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

Question

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.

@cricket_007 I think there is a method, which like binary search. The search begins in the middle... — xirururu, Mar 21 '16 at 23:02
https://stackoverflow.com/questions/9706041/finding-index-of-an-item-closest-to-the-value-in-a-list-thats-not-entirely-sort ? — sancho.s ReinstateMonicaCellio, Nov 14 '17 at 09:00
Does this answer your question? [Find next lower item in a sorted list](https://stackoverflow.com/questions/2591159/find-next-lower-item-in-a-sorted-list) — user202729, Mar 01 '21 at 00:32

Simeon Visser · Accepted Answer · 2016-03-21T23:03:50.863

10

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.

edited Mar 21 '16 at 23:03

answered Mar 21 '16 at 23:02

Simeon Visser

118,920
18
185
180

2

This is as fast as it gets, takes O(log n) time. – jayelm Mar 21 '16 at 23:03

OneCricketeer · Answer 2 · 2016-03-22T00:15:46.970

Manually implemented binary search

def find_largest_less_than(l, max_val, lo=0, hi=None):
    if hi is None:
        hi = len(l)

    if lo > hi: return None
    if hi - lo == 1: return None if max_val < l[lo] else l[lo]

    mid = lo + ((hi - lo) // 2)
    mid_val = l[mid]

    if max_val > mid_val:
        val = find_largest_less_than(l, max_val, mid, hi)
    elif max_val < mid_val:
        val = find_largest_less_than(l, max_val, 0, mid)

    return val

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

find_largest_less_than(mysortedList, my_max) # 645

Joe T. Boka · Answer 3 · 2016-03-21T23:05:06.350

-2

You can use list comprehension:

>>> lst = [i for i in mysortedList if i <= 700]
>>> lst[-1]

edited Mar 21 '16 at 23:05

answered Mar 21 '16 at 23:02

Joe T. Boka

6,554
6
29
48

3

This will trasverse all items in the list, even if it has found the number halfway through. The OP said his list has millions of elements. – Reti43 Mar 21 '16 at 23:04
1

@Reti43 The OP didn't mention millions of elements in his post. I didn't read the comments. My bad! – Joe T. Boka Mar 21 '16 at 23:10
No worries. My comment only served to bring this to your attention for this exact reason. – Reti43 Mar 21 '16 at 23:15
@Reti43 Thanks! I appreciate it. – Joe T. Boka Mar 21 '16 at 23:22

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

3 Answers3

Linked