Binary Search

How it works

Binary search keeps a range that is guaranteed to contain the answer and halves it with each test. Twenty steps cover a million candidates, thirty cover a billion, so it is the default whenever the input is sorted or the constraints rule out a linear scan.

The robust mental model is a boundary, not a lookup. Imagine a predicate that is false for every candidate up to some point and true from then on. Binary search finds the first true. Searching for a value, an insertion point, or the first bad version are all the same boundary search.

The same idea works on answers. If you can check 'is capacity c enough?' in linear time, and enough-ness only improves as c grows, then you binary search c across its possible range. This is how shipping, eating-speed and split-array problems are solved.

Look for sorted or rotated input, a phrase like 'minimum value such that', or limits up to 10^9 where only a logarithmic number of checks is affordable.

How to attack it

1. 1Identify the search space: indices of an array, or a numeric range of answers.
2. 2Write the predicate and confirm it is monotonic (false...false, true...true).
3. 3Choose the boundary you want: first true or last false.
4. 4Use one loop shape consistently and know what lo holds when it ends.
5. 5Test with one and two elements, and with the answer at either end.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def first_true(lo, hi, ok):
    # Smallest x in [lo, hi] with ok(x) True; returns hi + 1 if none.
    # Requires ok to be monotonic: False ... False True ... True.
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if ok(mid):
            hi = mid - 1   # mid works; look for an earlier one
        else:
            lo = mid + 1   # mid fails; the answer is to the right
    return lo


def lower_bound(nums, target):
    # First index whose value is >= target (insertion point).
    return first_true(0, len(nums) - 1, lambda i: nums[i] >= target)


def min_capacity(weights, days):
    # Binary search on the answer: the smallest capacity that fits in 'days'.
    def fits(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used, load = used + 1, 0
            load += w
        return used <= days
    return first_true(max(weights), sum(weights), fits)

What it costs