all Python 3bisectterm

Binary search with bisect

usage

bisect does not check whether the item is present, but a binary search can be built on it by checking the position it returns.

Syntax

i = bisect_left(a, x)
if i < len(a) and a[i] == x: found

Order the conditions carefully: i < len(a) must come first, or a[i] raises IndexError when x is larger than everything in the list. Use bisect_left specifically — bisect_right lands past the matching entry, forcing you to compare against a[i-1] instead. The whole point is trading the O(n) scan of x in a for an O(log n) probe, which only pays off on a list that is already sorted.

Examples

import bisect
def search(a, x):
    i = bisect.bisect_left(a, x)
    return i if i < len(a) and a[i] == x else -1
a = [1, 3, 5, 7, 9]
print(search(a, 5))  # → 2
print(search(a, 4))  # → -1
print(search(a, 9))  # → 4

See also

Open in the full glossarydocs.python.orgReport an inaccuracy