Binary search patterns

Binary search halves the search range at every step: O(log n). In interviews it appears in three disguises.

1. The first position that passes a test

The most useful form is not "find x" but: in a list where a test is false, false, ..., false, true, true, ..., true, find the first true. "The first number ≥ x" (Python's bisect_left), "the first bad version", "the first day the plants bloom" are all this.

def first_true(lo, hi, test):
    """The first value in [lo, hi) where test is true; hi if none is."""
    while lo < hi:
        mid = (lo + hi) // 2
        if test(mid):
            hi = mid          # mid works: the answer is mid or before it
        else:
            lo = mid + 1      # mid fails: the answer is after it
    return lo

nums = [1, 3, 3, 5, 8, 13]
print(first_true(0, len(nums), lambda i: nums[i] >= 4))   # first number >= 4: position 3
print(first_true(0, len(nums), lambda i: nums[i] >= 99))  # none: len(nums)
print(first_true(1, 100, lambda x: x * x >= 50))          # smallest x with x² >= 50

Two details make it bug-free: the range is half-open, lo to hi with hi excluded, and the loop ends when lo == hi, which is the answer (it is len(items) if no position passes). Off-by-one errors are the classic binary-search bug, so learn one template well and always use it.

2. A rotated sorted list

A sorted list was rotated: [4, 5, 6, 7, 0, 1, 2]. Find a target in O(log n).

Cut in the middle: one of the two halves is always sorted. If nums[lo] ≤ nums[mid], the left half is sorted; check whether the target lies in its range, and search there or in the other half. Otherwise the right half is sorted, and the same reasoning applies.

3. Binary search on the answer

Packages with weights w must ship in order within D days. What is the smallest ship capacity that makes it?

There is no list to search, but there is a test: "can capacity c do it in D days?" It is false for small c and true for large c, so binary search over c, from the heaviest package (smaller can never work) to the total weight (one day). Each test is a greedy O(n) pass.

def days_needed(weights, capacity):
    days, load = 1, 0
    for w in weights:
        if load + w > capacity:       # start a new day
            days += 1
            load = 0
        load += w
    return days

def least_capacity(weights, d):
    lo, hi = max(weights), sum(weights) + 1
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= d:
            hi = mid
        else:
            lo = mid + 1
    return lo

weights = [3, 2, 2, 4, 1, 4]
print(least_capacity(weights, 3))
print(days_needed(weights, 6), "days with capacity 6")

O(n log S), where S is the range of capacities. Watch for "the minimum value such that ..." or "the maximum value such that ..." with a test that only flips once: that is binary search on the answer.

Mark lesson complete