# Binary search in Python

I needed to do binary search of a sorted list with a custom comparator, something that isn’t supported by the Python standard library, so I’ve written a suite of functions for the purpose. They’re modeled on the C++ standard library functions lower_bound(), upper_bound(), equal_range(), and binary_search().

## lower_bound()

lower_bound() returns the index of the first element greater than or equal to the sought value, or the length of the list if it isn’t found:

def lower_bound(sequence, value, compare=cmp):
"""Find the index of the first element in sequence >= value"""
elements = len(sequence)
offset = 0
middle = 0
found = len(sequence)

while elements > 0:
middle = elements / 2
if compare(value, sequence[offset + middle]) > 0:
offset = offset + middle + 1
elements = elements - (middle + 1)
else:
found = offset + middle
elements = middle
return found


## upper_bound()

upper_bound() returns the index of the first element greater than the sought value, or the length of the list if there is no such value:

def upper_bound(sequence, value, compare=cmp):
"""Find the index of the first element in sequence > value"""
elements = len(sequence)
offset = 0
middle = 0
found = 0

while elements > 0:
middle = elements / 2
if compare(value, sequence[offset + middle]) < 0:
elements = middle
else:
offset = offset + middle + 1
found = offset
elements = elements - (middle + 1)
return found


## equal_range()

equal_range() returns a pair containing the results of lower_bound() and upper_bound(), so it defines the bounds of a slice whose elements are equal to the value:

def equal_range(sequence, value, compare=cmp):
"""Find the range of sequence equal to value"""
return lower_bound(sequence, value, compare), upper_bound(sequence, value, compare)


## binary_search()

binary_search() just returns a Boolean value indicating whether or not a value is present:

def binary_search(sequence, value, compare=cmp):
"""Find out if value is in sequence"""
index = lower_bound(sequence, value, compare)
return index < len(sequence) and compare(value, sequence[index]) == 0