Search code examples
pythonsearch

How to find the closest smaller value in a large sorted array efficiently

For a sorted list, how can I find the smallest number which close to the a given number?

For example,

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

How can I find the largest element which is less or equal to 700 quickly? (If I have 10 million elements, then it will be slow to search linearly). In this example, the answer is 645.

Solution

  • 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.