Finding Index of an Item Closest to the Value in a List That'S Not Entirely Sorted

Finding index of an item closest to the value in a list that's not entirely sorted

Try the following:

min(range(len(a)), key=lambda i: abs(a[i]-11.5))

For example:

>>> a = [25.75443, 26.7803, 25.79099, 24.17642, 24.3526, 22.79056, 20.84866, 19.49222, 18.38086, 18.0358, 16.57819, 15.71255, 14.79059, 13.64154, 13.09409, 12.18347, 11.33447, 10.32184, 9.544922, 8.813385, 8.181152, 6.983734, 6.048035, 5.505096, 4.65799]
>>> min(range(len(a)), key=lambda i: abs(a[i]-11.5))
16

Or to get the index and the value:

>>> min(enumerate(a), key=lambda x: abs(x[1]-11.5))
(16, 11.33447)

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

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

Efficient way to grab an index value

You did the entire thing, but took an extra step:

a = [(376, 220), (350, 218), (324, 216), (298, 214), (271, 211), (245, 210), (219, 208), (192, 205), (166, 204)]
to_find = (190, 210)

ix = min(range(len(a)), key = lambda x: abs(a[x][0] - to_find[0]))
print(ix)

Output:

7

Another way, would probably be faster:

a = [(376, 220), (350, 218), (324, 216), (298, 214), (271, 211), (245, 210), (219, 208), (192, 205), (166, 204)]
to_find = (190, 210)

min_diff, min_ix = 999999999, None
for ix, value in enumerate(a):
    diff = abs(to_find[0] - value[0])
    if diff < min_diff:
        min_diff, min_ix = diff, ix
print(min_ix)

How to find a value closest to another value X in a large sorted array efficiently

You can use the bisect module:

import bisect

data = [37, 72, 235, 645, 715, 767, 847, 905, 908, 960]

location = bisect.bisect_left(data, 700)

result = data[location - 1]

This is a module in the standard library which will use binary search to find the desired result. Depending on the exact value that you need you can also use bisect_right instead of bisect_left.

This is faster than iterating over the list because the binary search algorithm can skip parts of the data that won't contain the answer. This makes it very suitable for finding the nearest number when the data is known to be sorted.

Get index for closest value in array

Solved it with firstIndex. Not super elegant but it works.

func closestMatch(values: [Int], inputValue: Int) -> Int? {
    let match = values.reduce(values[0]) { abs($0-inputValue) < abs($1-inputValue) ? $0 : $1 }
    let index = values.firstIndex(where: {$0 == match})
    return index
}

Get Number Closest To Value - If Multiple Closest, Get All - Python

To find more than 1 minimum value we can use heapq.nsmallest function like

>>> myList = [1, 4, 5, 9, 10, 12, 15, 17]
>>> from heapq import nsmallest
>>> nsmallest(2, myList, key=lambda x: abs(x - 16))
[15, 17]

Find nearest value in numpy array

import numpy as np
def find_nearest(array, value):
    array = np.asarray(array)
    idx = (np.abs(array - value)).argmin()
    return array[idx]

Example usage:

array = np.random.random(10)
print(array)
# [ 0.21069679  0.61290182  0.63425412  0.84635244  0.91599191  0.00213826
#   0.17104965  0.56874386  0.57319379  0.28719469]

print(find_nearest(array, value=0.5))
# 0.568743859261

Find Index That Matches To Closest Provided Number Pairing

You could first find the euclidean distance between two points using sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2), then use it combined with min() as a key to find the closest point.

from math import sqrt

lats = [40.92322342,40.92322342,40.92322342,40.92322342,40.92322342]
lons = [-74.32176109,-74.29518277,-74.26860445,-74.24202613,-74.21544781]

def euclidean_distance(x, y):
    return sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2)

def find_closest_point(data, point):
    # create (point, index) pairs
    indices = ((e, i) for i, e in enumerate(data))

    # find smallest point, and only return the index
    return min(indices, key=lambda p: euclidean_distance(p[0], point))[1]

print(find_closest_point(zip(lats, lons), (40.9254, -74.2765)))

Which returns the third pair of coordinates(indexing starting at 0):

2

Note: You could have lats and lons in a list of tuples to begin with, then you don't need to call zip() in the function.

---

Related Topics