Binary search isn't an array trick — it's what you do to anything monotonic: a sorted array, a rotated one, or the space of possible answers itself. One six-line loop, learned once with its off-by-ones filed down, finds any yes/no boundary in O(log n).
Chapter 3 told you that n ≈ 10⁹ in the constraints leaves you two survivors: O(log n) and O(1). This chapter is the first survivor. Binary search is the only pattern in the book that routinely beats a billion elements before your coffee cools — thirty probes, done.
But the version most people carry around — "look for a value in a sorted array" — is the smallest room in the house. The full pattern is a boundary hunt on anything monotonic, and its best trick is searching arrays that were never built. We'll take it in three sittings: the discipline (so the off-by-ones stop biting), the rotated-array disguise, and search-on-answer — the superpower that comes back in Chapter 17 wearing a wetsuit.
You already play binary search at parties. "I'm thinking of a number from 1 to 100" — nobody guesses 1, then 2, then 3. You guess 50, hear "higher", and just deleted half the universe with one question. Seven questions finish 100 numbers; twenty finish a million; thirty finish a billion. That's O(log n) — halve the candidates per step, and the step count is "how many times can I halve n", which is log₂ n.
The party trick works because the oracle's answers are consistent with an ordering: "higher" doesn't just kill 50, it kills everything below 50. That's the real requirement — not "the input is a sorted array" but "one probe's answer tells me about half the candidates at once". Sorted arrays merely happen to be the most common place this holds. Keep that distinction warm; Section 5 cashes it in.
One more framing before the machinery. Every log you'll ever quote in an interview deserves a gloss, so here's this one: O(log n) — double the input, pay one more step. It's the complexity class that makes "the array has 10⁹ elements" a threat in every pattern except this one.
Here is the single reframe that retires 90% of binary-search bugs. Forget "find the value". Instead, picture a row of answers to some yes/no question, and notice that monotonicity forces them into two clean runs:
✗ ✗ ✗ ✗ ✗ ✗ ✓ ✓ ✓ ✓
All the noes, then all the yeses. Somewhere between them sits the boundary — the first ✓ — and that is what binary search finds. Every classic is this picture with a different question:
Why does this framing kill bugs? Because "find the value" has three outcomes to juggle (found it, go left, go right), while "find the first ✓" has exactly two: mid is a ✓ (the boundary is here or to the left) or mid is a ✗ (the boundary is strictly to the right). Two outcomes, two updates, no special cases. The loop practically writes itself — next section, it does.
Here's the loop, in the one shape this book will use everywhere. lo and hi bracket the candidates; the invariant — the sentence that stays true every lap — is "the boundary is somewhere in [lo, hi]":
while lo < hi: mid = (lo + hi) // 2; if check(mid): hi = mid; else: lo = mid + 1
Read the asymmetry — it's the whole trick. A ✓ at mid means mid might itself be the first ✓, so it must stay in the range: hi = mid, not mid − 1. A ✗ at mid means mid is definitely dead, so we may skip past it: lo = mid + 1. One side keeps mid, the other side buries it. The loop ends when lo == hi — a range of one candidate, which by the invariant must be the boundary.
And the classic terror — "does it loop forever?" — has a one-line audit: with a floor mid, mid < hi whenever the range has ≥ 2 elements, so hi = mid strictly shrinks the range, and lo = mid + 1 obviously does. Floor-mid pairs with hi = mid; that pairing is the immunization. Memorize the pair, not twelve variants.
Now go play the game below. You probe, the range shrinks, and the counter holds you to the mathematically fair budget of ⌈log₂ n⌉ probes. The part worth feeling in your hands: after each probe you choose which half survives — and the widget calls it out when you bury a candidate that might have been the answer.
Interviewers love breaking sortedness just a little. Take a sorted array, chop it once, swap the pieces: [4,5,6,7,0,1,2]. Search in Rotated Sorted Array Medium asks for a target in O(log n); Find Minimum in Rotated Sorted Array Medium asks where the scar is. A linear scan is off the table — the whole point is to halve anyway.
The saving grace, and the only new idea you need: cut a rotated array anywhere, and at least one of the two pieces is perfectly sorted. The scar can't be in both halves — there's only one scar. So each lap:
Find Minimum is the same insight aimed at the scar itself: the minimum is the one place where sortedness breaks, and "is a[mid] ≤ a[hi]?" is a monotonic question about which side of the scar you're on — first-true thinking again, no target required.
Now the superpower. Koko Eating Bananas Medium: piles of bananas [3, 6, 7, 11], guards back in h hours, Koko eats at speed k bananas/hour (one pile at a time, a pile-hour is spent even if the pile runs out mid-hour). Find the minimum k that finishes in time. There is no array to search. Nothing is sorted. And yet this is the purest binary search in the book.
The move: search the space of candidate answers. Speeds run from 1 to max(pile) — faster than the biggest pile buys nothing. For any speed, the question "can Koko finish in h hours at speed k?" has a yes/no answer, and it's monotonic in k: eating faster never makes you slower. So the answer space looks like ✗ ✗ ✗ ✗ ✓ ✓ ✓ — infeasible speeds, then feasible ones — and "minimum feasible speed" is exactly the first-✓ boundary from Section 2. Same six lines; the only new work is writing check(k), here a one-liner: sum(ceil(p / k)) ≤ h.
Cost: O(n log m) — each probe walks the n piles once, and there are log₂(max pile) probes. The widget below draws the answer space Koko can't see: drag h to move the feasibility boundary, then watch the search hop straight to it.
Once you've decided to search the answer space, the six-line loop is boilerplate; all the actual thinking moves into check(k). Three design notes that cover nearly every problem in this family:
Costs compose politely: O(check) × O(log |answer space|). Even a millions-wide answer range contributes a factor of ~20 — the log is doing all the heavy lifting, which is why this pattern turns "optimize a continuous-feeling quantity" problems into linear scans with a hat on.
The problems interviewers actually reach for, and which room of the house each one lives in:
And a practical footnote: real codebases call a library — Python's bisect_left is precisely Section 2's first-✓ search. In interviews, mention it to show you know it exists, then write the loop anyway; the loop is what's being graded. (In Chapter 12 you'll meet the same halving idea frozen into a data structure — the BST.)
The deepest advice this chapter has: stop improvising binary searches. There are half a dozen popular variants (closed ranges, half-open ranges, lo ≤ hi loops, ±1 on both updates) and they're all correct in someone's hands — but mixing them mid-problem is where the infinite loops breed. Pick the first-true shape, drill it until your fingers own it, and reduce every new problem to "what's my candidate range, what's my check". Under interview adrenaline you don't rise to the occasion; you sink to your most-rehearsed loop. Make it this one.
The pattern, as a whiteboard skeleton:
The flagship, both languages. Watch the anatomy match the skeleton line for line: the candidate range is speeds 1..max(piles), the check is an integer-only hours(k) ≤ h (the (p + k − 1) // k idiom is ceiling division without floats — say that out loud, it's a fluency point), and the loop is the first-✓ shape from Section 3, unchanged. The Scala version makes the loop a tail-recursive shrink — same invariant, the recursion is the while.