Python Binary Search with bisect

Intermediate

The bisect module helps you work with data that is already sorted. Unlike sorted(), which creates an ordered list, bisect finds a boundary inside a sorted sequence. That boundary can support a lookup, a range table, or an insertion that preserves the existing order.

The boundary can be before, after, or between duplicates

The functions bisect_left() and bisect_right() return an index, not a Boolean and not the matching value. With duplicates, the left version points before the equal values; the right version points after them. The sequence must already be sorted according to the same ordering you use for the search.

from bisect import bisect_left, bisect_right
values = [1, 3, 3, 5]
position = ?
print(position)

Use the position to check for an exact match

An insertion point does not prove that the target exists. To perform an exact lookup, first make sure the position is inside the list, then compare the value at that position with the target. The bounds check must come first so a target larger than every item does not cause an IndexError.

from bisect import bisect_left
values = [10, 20, 30]
results = []
for target in (25, 50):
    position = bisect_left(values, target)
    found = ?
    results.append(found)
print(results)

Insert while preserving sorted order

Use insort() when you want to insert a value and keep the list sorted. Its search step is logarithmic, but moving list elements to open a slot takes linear time. If you are only making a one-off ordered result, sorted() is usually simpler; insort() is useful when a sorted list needs to be maintained as new values arrive.

from bisect import insort
scores = [10, 20, 30, 40]
?
print(scores)

Search and insert records with a key

When the list contains records, pass a key function that extracts the field used for ordering. Keep the list sorted by that same key before searching. One subtle difference matters: bisect_left() applies key to the stored elements but not to the search value, so pass the comparison key as the search value. insort() applies key to the new record during its search step, then inserts the original record.

Use boundaries for ranges

A boundary can select a category even when the number does not appear in the list. For example, sorted breakpoints can map a score to a grade range. This is different from an exact-value lookup: the insertion position itself tells you which interval contains the value.

Know the performance and safety limits

Binary search takes O(log n) comparisons, making it useful for finding boundaries in large sorted sequences. Inserting into a Python list is still O(n) because later elements shift. For frequent exact lookups by a unique key, a dictionary or set is often a better fit. Do not call bisect concurrently on a sequence that another thread may mutate; the module does not make shared-list operations thread-safe.

Choose the right tool

Use bisect when you need a boundary in data that is already sorted. Choose sorted() when you need a fully ordered result, and a dictionary or set when the main job is repeated exact membership or key lookup.