Binary search — every question, written out
Halve the search range with every probe. The most important loop invariant in interviewing, and the easiest to get subtly wrong. Twenty probes search a million.
Read the binary search explanation and watch it run
Why is binary search O(log n)? Derive it rather than reciting it.
Complexity derivation
Each probe discards at least half the surviving candidates, so k probes leave n / 2^k
One comparison against the midpoint eliminates that index and everything on one side of it, so at most half the candidates survive a probe. Starting from n, after k probes at most n / 2^k remain, and the loop must stop once that falls below one — giving k ≤ ⌈log₂ n⌉ + 1. Sortedness is what lets one comparison speak for a whole block; random access is what makes the midpoint reachable.
See it run — One comparison against a[7] paints indices 0–7 rejected: half the array, gone in a single step.
A sorted array holds one million entries. How many probes can a search need at worst?
Complexity derivation
About twenty, because 2²⁰ is just over a million
Twenty halvings shrink a million candidates to one, so the worst case is ⌈log₂ 1,000,000⌉ + 1, about twenty-one probes. The number is worth memorising because it makes the gap concrete: twenty looks against a million. Doubling the data adds exactly one probe, which is what logarithmic growth feels like in practice.
What space does binary search cost, and why does that question have two answers?
Complexity derivation
O(1) as a loop; O(log n) as a recursion, which spends stack frames for no benefit
The loop form keeps `lo`, `hi` and `mid` and nothing else, which is O(1) auxiliary space. The recursive form is tail-recursive, but in runtimes without tail-call elimination it still pushes a frame per probe, making it O(log n) for no gain in clarity. Prism runs the loop form for exactly that reason.
The data is unsorted and you need one lookup. Sort it and binary search, or just scan?
Trade-off & selection
Scan — sorting costs O(n log n), more than the O(n) scan it is meant to replace
Paying O(n log n) to save an O(n) scan loses on one lookup, so the scan wins outright. The sort earns its cost only when amortised: q lookups cost O(n log n + q log n) against O(q·n), and the crossover arrives quickly. The interview answer is that question — "how many searches?" — rather than a bound quoted in isolation.
A Java implementation computes `int mid = (lo + hi) / 2`. What is the defect?
Code diagnosis
`lo + hi` can exceed the maximum int, wrapping negative and indexing out of bounds
Once the array passes about a billion entries, `lo + hi` overflows a signed 32-bit int and wraps to a negative number, so `mid` addresses outside the array. Writing `lo + (hi - lo) / 2` computes the identical midpoint from a difference that cannot overflow, which is the form Prism shows in every language tab. The bug lived in the JDK’s own `binarySearch` for nine years, which is why interviewers still ask about one arithmetic expression.
Someone keeps `while (lo <= hi)` but updates with `hi = mid` rather than `hi = mid - 1`. What breaks?
Code diagnosis
On a one-element range whose value is too large, `hi` never moves and the loop spins forever
Termination rests on the range shrinking strictly on every iteration, which `mid ± 1` guarantees and `hi = mid` does not. When `lo == hi`, `mid` equals both of them, so `hi = mid` is a no-op and the loop condition stays true forever. The conventions must be paired: `lo <= hi` with `mid ± 1`, or `lo < hi` with `hi = mid` and a midpoint that rounds down.
Every element of a sixteen-element array equals the target. Which index does this code return?
Edge case reasoning
Index 7 — the first midpoint already matches, so it returns immediately
The equality test comes first, so the opening probe at the midpoint matches and the function returns index 7 after one comparison. That is right for "is it present?" and wrong for "where does the run start?", which is the distinction the lower-bound variant exists to draw. Prism’s all-equal preset makes the entire run twelve steps long, and the cell it marks is 7.
See it run — One probe, and the cell it marks as found is index 7 — the midpoint, not the first match.
So how do you make it return the FIRST index whose value is at least the target?
Trade-off & selection
Delete the early return: treat a match as a candidate and keep shrinking toward the left
The lower-bound form never returns early: a match means "this could be the answer, but something further left might also qualify", so the range keeps narrowing until one index remains. What is really being searched is the monotone predicate `a[i] >= target`, which is false and then true exactly once. Most real uses — insertion points, first occurrence, range queries — want this form, so it pays to learn it as the default and the plain search as the special case.
Now there is no array: find the smallest ship capacity that delivers every package within five days. Still binary search?
Trade-off & selection
Yes — capacity drives a monotone yes/no test, so the halving runs over candidate answers
Binary search needs an ordered range of candidates and a predicate that turns from no to yes exactly once — an array is only the most familiar instance of that. "Does capacity c finish in five days?" is monotone, since more capacity never hurts, so halving the range from the largest weight up to the total finds the boundary in log steps, each costing one O(n) simulation. Spotting that flip is the whole trick, and a large share of medium interview problems are this pattern in costume.
What is true at the top of every iteration of the loop?
Invariant identification
If the target is present at all, its index lies between `lo` and `hi` inclusive
The conditional is load-bearing: the claim is about where the target *would* be, so it stays true on a miss and turns into the conclusion once the range empties. Each update preserves it — `a[mid] < target` means no index up to `mid` can hold the target, so `lo = mid + 1` discards only impossible positions. Prism prints that sentence in the invariants panel as each bound moves.
See it run — The invariant after the first probe: nothing at or before index 7 can match.
Why is the loop guaranteed to finish, whether or not the target is present?
Invariant identification
Every iteration removes `mid` from the range, so the range strictly shrinks and must empty
The bound updates are `mid + 1` and `mid - 1`, so the probed index leaves the live range every single time and the range gets strictly smaller. A strictly decreasing non-negative size cannot decrease forever, and that is the entire termination argument. It is also why the off-by-one variants that keep `mid` inside the range can hang.
The values 1..16 are searched for 11. Which index does the first probe read, and why that one?
Trace prediction
Index 7: `lo + (hi − lo) / 2` with `lo = 0` and `hi = 15` rounds down to 7
The midpoint of `0..15` is `0 + (15 − 0) / 2 = 7` under integer division, so the first read is `a[7] = 8`. That value is below the target, which retires indices 0 through 7 on a single comparison. The trace’s `mid` pointer lands on 7 before any value has been read at all.
See it run — The mid pointer settles on index 7, chosen from the range alone.
The first probe rejected 0..7, leaving the live range 8..15. Which index is read next?
Trace prediction
Index 11 — the midpoint is recomputed from the surviving range, not the original one
`lo = 8` and `hi = 15`, so `mid = 8 + (15 − 8) / 2 = 11` and the probe reads `a[11] = 12`. That is above the target, so indices 11 through 15 are retired and `hi` drops to 10. Every probe is the midpoint of what is still alive, which is what keeps each comparison worth half the remaining work.
See it run — The second mid pointer: 11, the middle of 8..15 rather than of the whole array.
A hash table looks up in O(1). When is a sorted array plus binary search still the better structure?
Comparison
When queries involve ranges, neighbours or order statistics, which a hash cannot answer
A hash scatters keys deliberately, so it can answer "is 41 present?" and nothing else. "What is the smallest key above 41?" or "how many keys fall in 20..40?" need order, and a sorted array answers all of them with the same lower-bound search. Choose the hash for pure membership over a mutating set; choose sorted plus binary search the moment order is part of the question.
On a forty-element array a linear scan often beats binary search on the clock. Why?
Comparison
A scan walks contiguous memory the prefetcher predicts; each probe jumps somewhere unrelated
Big-O counts operations and says nothing about what one operation costs. Forty sequential reads live in a handful of cache lines the hardware fetches ahead of time, while six binary-search probes each stall on a cache miss. The logarithm wins asymptotically rather than universally, which is why real libraries fall back to scanning below a threshold.
The target is absent. What exactly ends the loop, and what has been proved when it does?
Edge case reasoning
`lo` passes `hi`, so the range is empty — and the invariant proves no such element exists
Each update pushes a bound past `mid`, so a range of size one becomes a range of size zero and `lo <= hi` fails. Emptiness together with the invariant is a proof rather than a shrug: every position that could have held the target was eliminated by a comparison speaking for a whole block. The lower-bound variant returns that empty position as an insertion point instead of −1, which is why it is the more useful of the two.
Explain binary search to someone who has never programmed. Say it out loud before revealing.
Explain it plainly
Think of a paper dictionary. You want ‘quixotic’, so you flop it open near the middle and land on ‘mango’. You do not read a single word of the first half — everything there comes before ‘m’, so your word cannot be hiding in it, and half the book is gone from one look. Open the middle of what is left, land on ‘tundra’, throw away everything after it. Twenty or so looks reaches any word in a million-word dictionary, because each look halves the pile instead of shaving one word off the front. Two places the picture cheats. The book has to be in order — do this to a shuffled dictionary and you will confidently report that ‘quixotic’ is not a word — and the story quietly assumes the word is in there. When it is not, the interesting part is that you end up with nowhere left to look, which is a proof of absence rather than a failure, and the empty gap you are staring at is exactly where the word would go if you were adding it.
The test is whether the listener could carry out the procedure and say why skipping so much is safe. A strong answer names the sorted precondition, the halving, and the fact that one look speaks for a whole block — then admits where the picture misleads, which is the miss.