bisect Binary Search

Concepts covered: Binary Search

On a sorted list, you can find where a value belongs without reading every item. Compare the target with the middle item: if the middle is smaller, the target belongs to its right; otherwise it belongs at or left of it. Each comparison halves what remains. The bisect module runs that loop in C; written out in Python, you can watch the range shrink.

sorted_ids = [3, 8, 15, 21, 34, 42, 57, 63]
target = 42
lo, hi = 0, len(sorted_ids)
while lo < hi:
    mid = (lo + hi) // 2
    print(lo, hi, mid, sorted_ids[mid])
    if sorted_ids[mid] < target:
        lo = mid + 1
    else:
        hi = mid
print("index:", lo)

0 8 4 34
5 8 6 57
5 6 5 42
index: 5

A list of 8 took 3 comparisons. Doubling the list adds 1 more comparison, so the count barely moves as data grows:

• 20
• 30

bisect_left and bisect_right

Both return an insertion index, the position where the value could go and keep the list sorted, and they differ only when the value is already present. bisect_left returns the index of the first equal item; bisect_right, also callable as bisect.bisect, returns the index right after the last one.

import bisect

ts = [100, 200, 200, 200, 350, 500]
print(bisect.bisect_left(ts, 200))
print(bisect.bisect_right(ts, 200))
print(bisect.bisect_left(ts, 250))
print(bisect.bisect_right(ts, 200) - bisect.bisect_left(ts, 200))

Output:

1
4
4
3

To check membership, compute i = bisect.bisect_left(ts, x) and then test i < len(ts) and ts[i] == x. The bounds check matters because a value above everything returns len(ts). To count values from lo up to but excluding hi, subtract: bisect_left(ts, hi) - bisect_left(ts, lo). On sorted event timestamps, that counts a time window's events with no loop.

import bisect

event_ts = [3, 8, 8, 15, 21, 30, 42]

def contains(sorted_list, x):
    i = bisect.bisect_left(sorted_list, x)
    return i < len(sorted_list) and sorted_list[i] == x

print(contains(event_ts, 15), contains(event_ts, 16), contains(event_ts, 99))
start, end = 8, 30
print(bisect.bisect_left(event_ts, end) - bisect.bisect_left(event_ts, start))

Output:

True False False
4

Bucketing values against thresholds

A sorted list of thresholds turns bisect_right into a decision table: the index it returns is the bucket number. A value equal to a threshold lands in the bucket above it; switch to bisect_left when boundary values belong below.

import bisect

limits = [100, 500, 2000]
labels = ["fast", "ok", "slow", "timeout"]
for ms in [40, 100, 1200, 2500]:
    print(ms, labels[bisect.bisect_right(limits, ms)])

Output:

40 fast
100 ok
1200 slow
2500 timeout

Inserting while staying sorted

bisect.insort(lst, x) finds the position with bisect_right and inserts there, so the list is sorted after every new item.

import bisect

scores = [72, 85, 91, 95]
bisect.insort(scores, 88)
print(scores)
bisect.insort(scores, 91)
print(scores)

built = []
for item in [5, 2, 8, 1]:
    bisect.insort(built, item)
    print(built)

[72, 85, 88, 91, 95]
[72, 85, 88, 91, 91, 95]
[5]
[2, 5]
[2, 5, 8]
[1, 2, 5, 8]

The search half of insort takes a few comparisons, but the insert half is list.insert, which shifts every later item like the front insert in the deque section. For a few thousand items that cost is small. When a large list takes many inserts, append everything and sort once; that is usually faster. If you only ever need the smallest item, use a heap instead.

Bisect never checks the order, so check it yourself once, where sorted data enters your code. all(a <= b for a, b in zip(ts, ts[1:])) compares each neighbouring pair and returns False at the first pair out of order. That pass reads the whole list, which is the cost bisect saves you, so run it when the list is built, never inside a loop of searches. A list kept only through insort stays sorted by construction and needs no check.

This list was never sorted. What does the program print?

import bisect

latencies = [50, 20, 90, 70]
print(bisect.bisect_left(latencies, 30))

• 2: bisect halves the list as given and never checks that it is sorted
• 1: bisect sorts a copy first, and 30 belongs at index 1 in that copy
• ValueError: bisect rejects a list that is not in ascending order
• 0: bisect scans from the left to the first value at or above 30

About this lesson

This section is part of the Collections: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.