Binary Search

Binary search doesn't need a sorted array. It needs something weaker and more powerful: a monotonic predicate — a yes/no question whose answers, laid across the search space, look like

F F F F F T T T T

— all false, then all true (or the reverse). One probe in the middle tells you which half the boundary lives in, so you discard the other half. Twenty probes cover a million candidates; forty cover a trillion.

A sorted array is just the special case where the predicate is nums[i] >= target. Hold onto the general form: any time you can phrase a problem as "find the first index/value where some condition flips from false to true," binary search applies — even when there is no array at all.

The principle: don't look for "sorted." Look for a question with one flip point.

Bugs in binary search come from not knowing what lo and hi mean. So decide their meaning first and never violate it:

Invariant: the answer is always inside [lo, hi). Everything left of lo is known-false; everything from hi onward is known-true.

def first_true(lo, hi, pred):       # search space [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid                # mid is true -> boundary is at mid or left of it
        else:
            lo = mid + 1            # mid is false -> boundary is strictly right
    return lo                       # first index where pred is true (== hi)

Every line is forced by the invariant:

• while lo < hi — when they meet, the window is empty and lo is the flip point. No <=, no separate exit checks.
• hi = mid (not mid - 1) — mid answered true, so it might be the boundary; the invariant says hi is known-true territory, and now it is.
• lo = mid + 1 — mid answered false, and the invariant says everything left of lo is false. Done.

The window shrinks every iteration (mid < hi always), so it can't loop forever. Classic find-the-target is this template with pred(i) = nums[i] >= target, plus one final equality check.

The principle: write the meaning of lo and hi as a comment before the loop. Each branch then writes itself, and you will never again debate < versus <= at a whiteboard.

The pattern that elevates binary search from "easy warm-up" to "medium killer": when a problem asks for the minimum value that satisfies a constraint, binary search over candidate answers.

The archetype: Koko has piles of bananas and h hours; eating at speed k she clears each pile in ceil(pile / k) hours. Find the minimum k that finishes in time.

There's no array of speeds to search — so build the predicate instead. can_finish(k) is monotonic: if speed k works, every faster speed works too. F F F T T T across the speeds. That's all binary search needs:

def min_speed(piles, h):
    def can_finish(k):
        return sum((p + k - 1) // k for p in piles) <= h

    lo, hi = 1, max(piles)          # answer lives in [lo, hi)... with hi+1 exclusive
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Cost: O(n log(max_pile)) — the predicate is O(n) and you call it ~30 times. The same skeleton solves "ship packages within D days," "split array to minimize largest sum," and "minimum time to make m bouquets." Different stories, identical bones: feasibility check + monotonicity + binary search on the answer.

The principle: when the question is "smallest X such that doable(X)," don't construct X — guess and verify, halving the guess range.

Take a sorted array and rotate it: [4, 5, 6, 7, 0, 1, 2]. Sortedness is broken — but not destroyed. Cut it anywhere and at least one half is still perfectly sorted. That salvaged structure is enough to keep halving.

Two staple problems:

Find the minimum. Compare nums[mid] to nums[hi] (the right end). If nums[mid] > nums[hi], the cliff — and the minimum — is to the right of mid. Otherwise the minimum is at mid or left of it. Note the predicate "am I in the right, smaller run?" is monotonic across the array: it's the template again in disguise.

lo, hi = 0, len(nums) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1
    else:
        hi = mid
# nums[lo] is the minimum

Find a target. At each step, check which half of [lo, mid, hi] is sorted (compare the endpoints). If the target lies inside that sorted half's range, search it; otherwise search the messy half — which is itself a rotated array, so the logic recurses cleanly.

Why compare against nums[hi] and not nums[lo] when finding the minimum? An unrotated array breaks the nums[lo] version. Test your code on the boring case: rotation of zero.

The principle: when structure is damaged, find the part that survived. Binary search only needs one reliable comparison per step — not a globally sorted world.