CODEWITHSUNDEEP
pythonpython-3.xlist
user94758
user94758

Reputation: 107

In a python list which is sorted, find the closest value to target value and its index in the list

I am trying to get both the closest value and its index in a sorted list in python.

In MATLAB this is possible with:

[closest_val,index] = min(abs(array - target))

I was wondering if there is a similar way this can be implemented in python.

I've seen posts which do one or the other, but I haven't seen both done together.

Link to finding closest value in list post.

Upvotes: 0

Views: 2952

Answers (2)

hiro protagonist
hiro protagonist

Reputation: 46849

this is an option:

lst = [
    13.09409,
    12.18347,
    11.33447,
    10.32184,
    9.544922,
    8.813385,
]

target = 11.5

res = min(enumerate(lst), key=lambda x: abs(target - x[1]))
# (2, 11.33447)

enumerate iterates over your list in index, value pairs. the key of the min method tells it to only consider the value.

note that python starts indexing at 0; matlab at 1 as far as i remember. if you want that same behavior:

res = min(enumerate(lst, start=1), key=lambda x: abs(target - x[1]))
# (3, 11.33447)

if the list is big, i strongly suggest you use bisect as suggested in this answer.

Upvotes: 6

Amadan
Amadan

Reputation: 198324

bisect wasn't used in the linked question because the list was not sorted. Here, we don't have the same problem, and we can use bisect for the speed it provides:

import bisect

def find_closest_index(a, x):
    i = bisect.bisect_left(a, x)
    if i >= len(a):
        i = len(a) - 1
    elif i and a[i] - x > x - a[i - 1]:
        i = i - 1
    return (i, a[i])

find_closest_index([1, 2, 3, 7, 10, 11], 0)   # => 0, 1
find_closest_index([1, 2, 3, 7, 10, 11], 7)   # => 3, 7
find_closest_index([1, 2, 3, 7, 10, 11], 8)   # => 3, 7
find_closest_index([1, 2, 3, 7, 10, 11], 9)   # => 4, 10
find_closest_index([1, 2, 3, 7, 10, 11], 12)  # => 5, 11

EDIT: In case of descending array:

def bisect_left_rev(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] > x: lo = mid+1
        else: hi = mid
    return lo

def find_closest_index_rev(a, x):
    i = bisect_left_rev(a, x)
    if i >= len(a):
        i = len(a) - 1
    elif i and a[i] - x < x - a[i - 1]:
        i = i - 1
    return (i, a[i])

find_closest_index_rev([11, 10, 7, 3, 2, 1], 0)   # => 5, 1
find_closest_index_rev([11, 10, 7, 3, 2, 1], 7)   # => 2, 7
find_closest_index_rev([11, 10, 7, 3, 2, 1], 8)   # => 2, 7
find_closest_index_rev([11, 10, 7, 3, 2, 1], 9)   # => 1, 10
find_closest_index_rev([11, 10, 7, 3, 2, 1], 12)  # => 0, 11

Upvotes: 4

Related Questions