Python Return closest number above and below given x

Question

I have a problem. In my code I need to do the following: I have an array like this: [1, 5, 7, 9, 10, 11, 14, 15]

Now I need to determine in the most efficient way what the closest values are for a given x. For example:

array = [1, 5, 7, 9, 10, 11, 14, 15]
above, below = myFunction(array, 8)

Should return 7 and 9

If there is no number higher or lower than the given number, the value that couldn't be determined should be None. If the same number is given as in the array, for example: 7. The values 5 and 9 should be returned.

I know there is a min() and max() function, but I couldn't find anything in my case. The only thing close to what I want, was manual looping through the array, but I was wondering if there was a more efficient way, because this code will be executed arround 500.000 times, so speed is important!

Is there a efficient way to determine those values?

Answer 1

import bisect

def find_nearest(arr,value):
    arr.sort()
    idx = bisect.bisect_left(arr, value)

    if idx == 0:
        return None, arr[idx]
    elif idx == len(arr):
        return arr[idx - 1], None
    elif arr[idx] == value:
        return arr[idx], arr[idx]
    else:
        return arr[idx - 1], arr[idx]

array = [1, 5, 7, 9, 10, 11, 14, 15]

print(find_nearest(array, 0))
print(find_nearest(array, 4))
print(find_nearest(array, 8))
print(find_nearest(array, 10))
print(find_nearest(array, 20))

Output:

(None, 1)
(1, 5)
(7, 9)
(10, 10)
(15, None)

Helper source

Answer 2

Assuming that your array is not sorted, you will be indeed forced to scan the entire array. But if it is sorted you can use a binary search approach that will run in O(log(n)), something like this:

def search_nearest_elems(array, elem):
    """
    Uses dichotomic search approach.
    Runs in O(log(n)), with n = len(array)
    """
    i = len(array) // 2
    left, right = 0, len(array) - 1
    while right - left > 1:
        if array[i] == elem:
            return elem, elem
        elif array[i] > elem:
            right, i = i, (left + i) // 2
        else:
            left, i = i, (right + i) // 2

    return array[left], array[right]

array = [1, 5, 7, 9, 10, 11, 14, 15]
assert search_nearest_elems(array, 8) == (7, 9)
assert search_nearest_elems(array, 9) == (9, 9)
assert search_nearest_elems(array, 14.5) == (14, 15)
assert search_nearest_elems(array, 2) == (1, 5)

Answer 3

This answer based on @Mark Tolonen hint about bisect

Let's say that you need to append one number on every iteration but initial array is the same.
All elements in array should be unique. Initial array may be not sorted.

import bisect as b


init_array = [5, 9, 10, 11, 14, 15, 1, 7]

init_array.sort()

numbers_to_append = [22, 4, 12, 88, 99, 109, 999, 1000, 1001]

numbers_to_check = [12, 55, 23, 55, 0, 55, 10, 999]

for (_, n) in enumerate(numbers_to_check):

  # get index of closer right to below
  i = b.bisect_left(init_array, n)

  # get above
  if i >= (len(init_array)):
    above = None
  else:
    if init_array[i] == n:
      try:
        above = init_array[i + 1]
      except IndexError:
        above = None
    else:
      above = init_array[i]

  # get below
  below = init_array[i - 1] if i - 1 >= 0 and init_array[i - 1] - n < 0 else None

  print('---------')
  print('array is', init_array)
  print('given x is', n)
  print('below is', below)
  print('above is', above)
  print('appending', numbers_to_append[_])

  # check if number trying to append doesn't exists in array
  # WARNING: this check may be slow and added only for showing that we need to add only unique numbers
  # real check should be based on real conditions and numbers that we suppose to add
  i_to_append = b.bisect_left(init_array, numbers_to_append[_])
  if numbers_to_append[_] not in init_array[i_to_append:i_to_append+1]:
    init_array.insert(i_to_append, numbers_to_append[_])

output:

---------
array is [1, 5, 7, 9, 10, 11, 14, 15]
given x is 12
below is 11
above is 14
appending 22
---------
array is [1, 5, 7, 9, 10, 11, 14, 15, 22]
given x is 55
below is 22
above is None
appending 4
---------
array is [1, 4, 5, 7, 9, 10, 11, 14, 15, 22]
given x is 23
below is 22
above is None
appending 12
---------
array is [1, 4, 5, 7, 9, 10, 11, 12, 14, 15, 22]
given x is 55
below is 22
above is None
appending 88
---------
array is [1, 4, 5, 7, 9, 10, 11, 12, 14, 15, 22, 88]
given x is 0
below is None
above is 1
appending 99
---------
array is [1, 4, 5, 7, 9, 10, 11, 12, 14, 15, 22, 88, 99]
given x is 55
below is 22
above is 88
appending 109
---------
array is [1, 4, 5, 7, 9, 10, 11, 12, 14, 15, 22, 88, 99, 109]
given x is 10
below is 9
above is 11
appending 999
---------
array is [1, 4, 5, 7, 9, 10, 11, 12, 14, 15, 22, 88, 99, 109, 999]
given x is 999
below is 109
above is None
appending 1000