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