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