3

There's already a topic on how to do a binary search in Python if a list is sorted in ascending order, using the bisect module: Binary search (bisection) in Python

Is there a good way to do a binary search on a list that is sorted reverse?

Community
  • 1
  • 1
Ant6n
  • 1,887
  • 1
  • 20
  • 26

2 Answers2

3

This is what the documentations says about it:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

So it does not support custom order. Any attempt to get around it (such as reversing the list twice, or preparing a separate list of keys) would take linear time, which completely ruins the point of the binary search, which is logarithmic.

Here's an implementation of binary search that accepts a comparator

def bisect(arr, val, cmp):
    l = -1
    r = len(arr)
    while r - l > 1:
        e = (l + r) >> 1
        if cmp(arr[e], val): l = e
        else: r = e
    return r

It behaves like bisect_right, return l at the end if you need bisect_left. Here's an example usage on a reversed array:

>>> a = [10**8 - x for x in range(10**8)]
>>> bisect(a, 100, lambda x, y: x > y)
99999900
Ishamael
  • 12,583
  • 4
  • 34
  • 52
  • 1
    Haha, your Python implementation was faster than mine... Deleted my answer. – Alex Mar 14 '15 at 06:03
  • It still surprises me that two array reverses, that also presumably allocate memory, was faster than one list.index, which is just one scan. I would not believe it if I didn't see it with my own eyes. – Ishamael Mar 14 '15 at 06:05
  • Agreed... Must be the comparisons that are expensive. – Alex Mar 14 '15 at 06:11
0

In such cases, it is beneficial to have code snippets to replicate the library functions, e.g. bisect_left and bisect_right below. By changing < (or <=) to > (or >=), one obtains the bisection search for arrays of descending order. 

def bisect_left(a, x, lo=0, hi=None):
    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 bisect_right(a, x, lo=0, hi=None):
    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
Sam
  • 791
  • 6
  • 9