Searching guide · 6/6

Searching in the Real World

Binary search is far more than an interview trick. It sits inside databases, version control, networking and load balancing. This chapter covers where searching shows up in real systems and the pitfalls that come up most often in production code.

Searching inside real systems

Database indexes: a B-tree index stores sorted keys in each node (page) and uses binary search within a node to choose the child to descend into. Range queries such as WHERE price BETWEEN 100 AND 200 are fast precisely because the keys are kept in order.
LSM-tree storage: engines such as RocksDB keep a block index for each sorted file (SSTable) and binary search it to find the right block. A Bloom filter in front cuts the cost of looking up keys that are not there.
Standard libraries: Python bisect, C++ std::lower_bound and std::equal_range, Java Arrays.binarySearch and Collections.binarySearch, and Rust slice::binary_search and partition_point all apply the same idea.
Version control: git bisect binary searches the history between a known good and a known bad commit to find the commit that introduced a bug.
Weighted random selection: binary searching a random number in a prefix-sum array picks items in proportion to their weights. Python's random.choices uses bisect internally for this.

Hunting regressions with git bisect

Even with 1,000 commits in between, about 10 checks are enough to find the first bad commit, and the checks can be scripted.

git bisect start
git bisect bad                  # the current commit is broken
git bisect good v1.4.0          # this tag was known to work
# test each commit Git checks out, then mark it
git bisect good                 # or: git bisect bad
# automate with a test command: exit 0 = good, 1-127 except 125 = bad
git bisect run python -m pytest tests/test_parser.py -x -q
git bisect reset

Looking up IP address ranges

Finding which of many non-overlapping address ranges contains an IP is the problem "find the last range whose start is at most this address". Even with hundreds of thousands of ranges, each lookup is O(log n).

from bisect import bisect_right
from ipaddress import ip_address

ranges = [  # (start, end, label), sorted by start, non-overlapping
    (int(ip_address("10.0.0.0")), int(ip_address("10.255.255.255")), "internal"),
    (int(ip_address("192.168.0.0")), int(ip_address("192.168.255.255")), "lab"),
    (int(ip_address("203.0.113.0")), int(ip_address("203.0.113.255")), "docs"),
]
starts = [start for start, _, _ in ranges]


def lookup(ip):
    n = int(ip_address(ip))
    i = bisect_right(starts, n) - 1
    if i >= 0 and n <= ranges[i][1]:
        return ranges[i][2]
    return None


print(lookup("10.1.2.3"), lookup("192.168.5.5"), lookup("8.8.8.8"))
# internal lab None

Picking servers by weight

import random
from bisect import bisect_right
from itertools import accumulate

servers = ["a", "b", "c"]
cumulative = list(accumulate([5, 3, 2]))   # [5, 8, 10]


def pick():
    r = random.random() * cumulative[-1]     # 0 <= r < 10
    return servers[bisect_right(cumulative, r)]


counts = {s: 0 for s in servers}
for _ in range(10_000):
    counts[pick()] += 1
print(counts)   # roughly a 5000, b 3000, c 2000

When r is in [0, 5) you get a, in [5, 8) you get b, and otherwise c. At exactly 5 the pick must be b, which is why the code uses bisect_right rather than bisect_left.

Common pitfalls

Unsorted input: binary search raises no error; it just returns a wrong answer. Assert or document the sortedness assumption.
Mismatched ordering: if the data was sorted case-insensitively, by locale collation, or by a custom key, the search must compare the same way. Since Python 3.10, bisect accepts a key argument.
Off-by-one and infinite loops: do not mix closed and half-open intervals, and avoid updates such as lo = mid that may not shrink the range.
Integer overflow: in fixed-width integer languages, use lo + (hi - lo) / 2.
Floating point: when searching over real numbers, stop after a fixed number of iterations or at a tolerance instead of relying on lo < hi.
Linear search inside a loop: x in some_list inside a loop makes the whole thing O(n^2). Switch to a set when you only need exact matches.

Summary

B-tree indexes, SSTables, standard libraries, git bisect and weighted selection are all binary search over sorted order.
Range lookups and "latest value before" queries keep appearing in the form bisect_right(...) - 1.
Checking the sortedness assumption, the comparison order, the interval convention, overflow and real-number stopping rules prevents most search bugs.