Binary search has nothing to do with sorted arrays

For a long time I had a wrong rule in my head, and it was a reasonable wrong rule: if a problem asks me to minimize or maximize something, that's optimization, and optimization means greedy or DP. Min/max was build-the-answer territory. So when I'd hit a problem like "what's the minimum speed such that you finish in time," I'd start hunting for a recurrence — what's the subproblem, what's the state — and find nothing that fit. There was no clean subproblem because the problem wasn't built that way.

The thing that dissolved the confusion wasn't a new trick. It was someone drawing a line I hadn't known was there: the line between building an answer and searching for one. Min/max sits on both sides of that line. That shared keyword is exactly the trap.

Build versus search

Here's the distinction, as sharply as I can put it.

In greedy and DP, the answer is constructed. You combine the answers to smaller pieces — subproblem results, a running best — and the structure of the problem produces the value. You don't know the answer until the construction finishes; the construction is the computation. (Greedy is the same construction with a proof that local choices are safe.)

In binary search on the answer, nothing gets constructed. The answer already lives somewhere in a known range — some speed between 1 and the biggest pile, some capacity between the heaviest item and the total weight. You don't compute it. You guess a value and ask a cheap yes/no question: does this candidate work? Then you guess again, narrowing the range, until the range collapses onto the boundary.

The mental shift is that "minimize X" stops being "compute the smallest X" and becomes "find the boundary between the X values that fail and the X values that pass." Those are different verbs. One produces a number. The other locates a frontier.

The condition that makes search legal

A binary search needs order. In a sorted array, the array gives you the order for free — that's why the technique got filed there. But the order you actually need isn't in the data. It's in the answer.

What makes the answer space searchable is monotonicity of the validity check. Picture every candidate value laid out on a line and label each one pass or fail:

candidate:   1   2   3   4   5   6   7   8
isValid:     N   N   N   N   Y   Y   Y   Y
                          ^
                          the boundary you want

If isValid flips from N to Y exactly once and never flips back, the candidates are effectively sorted by a single boolean — and a single boolean in sorted order is the only thing binary search ever needed. There was never a real requirement for an array. The array was just the most common place this property showed up.

If the column were N Y N Y Y N, binary search is meaningless: there's no single boundary to find, and bisecting tells you nothing about the halves you discard. Monotonicity is not a nicety here. It's the entire license to search.

The three-question checklist

This is the test I locked in, and I run it before writing a line:

1. Does it ask for a min or max?
   The phrasing to listen for is "minimum/maximum X such that a condition holds." That "such that" is doing real work — it means the value is gated by a condition, not assembled from parts.
2. Can I write isValid(candidate) cheaply?
   Given a fixed candidate value, can I check yes/no whether it satisfies the condition, typically in O(n)? If checking one candidate is itself hard, this pattern won't save me.
3. Is isValid monotonic across the range?
   If a candidate passes, does every larger (or every smaller) candidate also pass? If yes, there's exactly one boundary, and it's findable by bisection.

All three yes, and you binary-search the answer space. Notice what the checklist does: it never asks you to find a recurrence or prove an exchange argument. It asks whether you can recognize a valid answer when handed one — a strictly easier job than producing one. That asymmetry is the whole payoff. Verifying is cheaper than constructing, and this pattern cashes that in.

A worked example

Take the eating-speed problem: there are piles of bananas and a fixed number of hours, and you want the smallest integer speed such that every pile is finished within those hours. At one banana per hour you'll surely run out of time; at a speed equal to the largest pile you'll clearly finish; the answer is somewhere between.

Run the checklist. Min? Yes. Cheap checker? Given a speed, I can compute the hours that speed requires in one pass over the piles. Monotonic? Yes — a faster speed never needs more hours, so once a speed is fast enough, every faster speed is too. Three yeses.

The checker just sums up, for each pile, how many hours that pile takes at the given speed:

func canFinish(piles: [Int], speed: Int, within hours: Int) -> Bool {
    var needed = 0
    for pile in piles {
        // ceil(pile / speed): a partial pile still costs a full hour
        needed += (pile + speed - 1) / speed
    }
    return needed <= hours
}

That single ceil line is the only non-obvious part: a pile of 7 at speed 3 is three hours, not two, because the leftover banana still occupies an hour. Now bisect the speed range, looking for the leftmost speed that passes:

func minSpeed(piles: [Int], hours: Int) -> Int {
    var lo = 1
    var hi = piles.max()!
    while lo < hi {                       // converge to a single survivor
        let mid = lo + (hi - lo) / 2
        if canFinish(piles: piles, speed: mid, within: hours) {
            hi = mid                      // mid works; it might be the answer, keep it
        } else {
            lo = mid + 1                  // mid fails; the answer is strictly larger
        }
    }
    return lo
}

The exact same skeleton solves the ship-within-D-days problem: candidate is a daily capacity, isValid sweeps the items counting how many days that capacity needs, monotonic because more capacity never costs more days. Different problem, identical machinery — because both are "minimum X such that a condition holds" over a monotonic check. Once you see the shape, the surface story stops mattering.

The honest sharp edge

Boundary-finding binary search is where off-by-one bugs live, and I won't pretend otherwise. The classic mid == target exit doesn't apply — there's no single target, there's a frontier, and you want the first cell on the pass side. Three details decide whether you land on it:

The load-bearing choice is hi = mid, not hi = mid - 1, when a candidate passes. A passing candidate is itself a contender for the smallest passing value, so you must not discard it — you shrink the range up to and including it. Pair that with lo < hi and computing mid with lo + (hi - lo) / 2, and the window closes onto exactly the boundary. Get the asymmetry wrong and you either skip the answer or loop forever. There's no shame in tracing it by hand on a three-element range; I still do.

Sibling patterns in this series: greedy and DP — the two build-the-answer tools this one is so easily confused with.

Problems to practice