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?
Add a comment
|
2 Answers
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
3 Comments
Alex
Haha, your Python implementation was faster than mine... Deleted my answer.
Ishamael
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.
Alex
Agreed... Must be the comparisons that are expensive.
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
