0

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.

user94758
  • 97
  • 1
  • 1
  • 8
  • Possible duplicate of [finding index of an item closest to the value in a list that's not entirely sorted](https://stackoverflow.com/questions/9706041/finding-index-of-an-item-closest-to-the-value-in-a-list-thats-not-entirely-sort) – wovano May 28 '19 at 05:18
  • @wovano: Not a dupe, as OP specifically notes it's similar, and yet explicitly notes that this is for a list that _is_ sorted. – Amadan May 28 '19 at 05:19
  • The accepted answer in the link actually returns the closest value and its index. Is that answer not acceptable? That solution also works for sorted lists. If there are any other requirements (like performance?), I think these should be added to this question to make it different. – wovano May 28 '19 at 05:20
  • @wovano: That answer is suboptimal for these circumstances, as quoted in my own answer. Or if an analogy will help, "How do you eat soup" is not a dupe of "How do you drink lemonade", despite that the latter's answer "through a straw" works with soup as well (one would hope for an answer of "using a spoon", which fits soups better). – Amadan May 28 '19 at 05:22
  • I understand that someone might want a better or optimal solution, but the question at this moment only states "I've seen posts which do one or the other, but I haven't seen both done together." which does not seem to be true. I'm suggesting that the question should be improved with additional criteria to make the question different. – wovano May 28 '19 at 05:30
  • See also https://stackoverflow.com/questions/6065697/python-numpy-quickly-find-the-index-in-an-array-closest-to-some-value – wovano May 28 '19 at 05:41
  • @wovano: A much better candidate for a dupe... except that the accepted answer is wrong. – Amadan May 28 '19 at 05:48

2 Answers2

6

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.

hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
3

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
Amadan
  • 191,408
  • 23
  • 240
  • 301
  • Is this method faster than the method posted by @hiro? I will likely be doing this on a list which has around 1000 - 2000 entries. – user94758 May 28 '19 at 05:22
  • On my computer, searching for a random number on array of size 2000 is 37x faster with my method, on the average (on 100 samples). It will be even faster on larger arrays. The reason is that `bisect` works entirely in C, while Hiro's method is largely dependent on Python; and `bisect` is `O(log N)`, while Hiro's is `O(N)`. – Amadan May 28 '19 at 05:34
  • yes, if your list is sorted to begin with (and speed is an issue) i strongly suggest you use `bisect`! good one! +1 – hiro protagonist May 28 '19 at 05:40
  • it seems like it doesn't work for negative numbers. One of the list I'm using it on starts off with positive floats but they decrease in value and become negative. – user94758 May 28 '19 at 05:42
  • Please be precise. I can't see the error, and I am not going to test for all combinations of all negative numbers. Instead of "doesn't work", could you rather give an example of something you tried that gives the wrong result? – Amadan May 28 '19 at 05:44
  • I created a test function where y = -1.1x + 1. And I created a list with size 2000 which is filled with values from that function. Then I was testing the function with random negative target values but the solution always points to the last index of the list. – user94758 May 28 '19 at 05:46
  • It's not that it doesn't work with negative values - it doesn't work with arrays that are not sorted in the _ascending order_. I apologise, I assumed so. The easiest way out is to reverse the list, and then reverse the index again after the application of my function; however, that makes it O(N), and Hiro's approach becomes better - unless you do it multiple times on the same list, allowing you to cache the reversed copy, in which my method can again show its benefits. Or you can reimplement `bisect_left` (as it's in Python code - apologies, I was wrong above). – Amadan May 28 '19 at 05:51
  • I added the implementation for descending arrays. – Amadan May 28 '19 at 06:15
  • Thanks mate, your solution works. The speed up will also be helpful as the list will accessed a lot. – user94758 May 28 '19 at 07:06