Fastest way to find which two elements of a list another item is closest to in python

Question

The input is a sorted list of elements and an external item. For example:

list_ = [0, 3.5, 5.8, 6.2, 88]
item = 4.4

What is the fastest way of finding out which two elements in list_ item falls between? In this case for example, the two numbers would be 3.5 and 5.8. Any ideas?

Answer 1

Since the input is sorted, you're best bet algorithmically is to use the bisect module -- e.g. bisect_left

>>> list_ = [0, 3.5, 5.8, 6.2, 88]
>>> item = 4.4
>>> bisect.bisect_left(list_, item)
2

The items you want reside at indices bisect_left(list_, item) and
bisect_left(list_, item) - 1

This should give you a result in O(logN) searches -- It doesn't get much better than that from an algorithm standpoint.

Answer 2

You can use bisect module's bisect function to get the index at which the item fits in

list_, item = [0, 3.5, 5.8, 6.2, 88], 4.4
from bisect import bisect
print bisect(list_, item)
# 2

Remember Your list_ has to be sorted, to be able to use the functions in bisect module.