Why does binary search need only about log2(n) comparisons where a linear scan needs n?

## What binary search actually does Binary search maintains a **candidate range** — a contiguous stretch of positions that could still hold the target — described by two bounds, conventionally `lo` and `hi`. Every iteration picks the midpoint of that range, compares the target against the value stored there, and uses the three-way outcome: - equal — the search is over, the position is the answer; - the midpoint value is **smaller** than the target — because the data is ordered, everything from `lo` up to and including the midpoint is too small, so the new range starts just after the midpoint; - the midpoint value is **larger** — everything from the midpoint to `hi` is too large, so the new range ends just before the midpoint. The important word is *including*. Each comparison throws away one half **plus the midpoint itself**, so the range strictly shrinks every single iteration. That is what guarantees the loop finishes at all. ## The halving argument Start with `n` candidate positions. After one comparison at most `n/2` remain. After two, at most `n/4`. After `k` comparisons, at most `n / 2^k` remain. The search cannot continue once the range is empty, so the question "how many comparisons in the worst case?" becomes "how many times can you halve `n` before nothing is left?" Solve `n / 2^k <= 1` for `k` and you get `k >= log2(n)`. That is the whole complexity proof — no recurrence machinery required. The worst-case number of probes is about `log2(n)`, and the standard closed form is `floor(log2(n)) + 1`. Compare that with a linear scan, which discards exactly **one** candidate per comparison. Its remaining range after `k` comparisons is `n - k`, so it needs `n` comparisons in the worst case. Subtraction versus division is the entire difference between the two algorithms. ## Why the numbers feel unreasonable The phone-book framing is the one to keep in your pocket. A paper directory of a million names: open it near the middle, see whether the name you want sorts before or after the page you landed on, tear away the half that cannot contain it, and repeat. Twenty tears settle a million names, because 2^20 = 1,048,576. Nobody would believe that from the algorithm's description alone; everyone believes it after doing it once with a book. The same arithmetic run backwards is the useful interview reflex: doubling the input adds **one** comparison, because one extra halving absorbs the extra data. That is the practical meaning of logarithmic growth, and it is why binary search does not care much whether your directory has a million entries or a hundred million. ## What the argument silently assumes Two preconditions carry the whole result, and a candidate who states them unprompted stands out. **Order by the compared key.** The midpoint comparison is only informative because sortedness lets one look at one position rule out an entire side. On unordered data the middle element tells you nothing about where the target lives, so no halving is available and you are back to scanning. Note the order must be on *the key you are searching by* — data sorted by some other field is unsorted as far as this search is concerned. **Cheap access to the midpoint.** The halving argument counts *comparisons*. It quietly assumes that jumping to the middle position costs about the same as jumping to any other one. When that is false — when reaching a midpoint means walking to it — the comparison count stays logarithmic but the real work does not. ## Misreadings to avoid The range does not need to be a power of two; integer division of an odd-sized range simply leaves one side one element larger, and `n / 2^k` remains an upper bound either way. The `log2(n)` figure is not an average over lucky inputs — it is the worst case, and the worst case is typically an **absent** target, where the range has to shrink all the way to empty before the algorithm can answer. And `log2(n)` is not `n/2`: halving *once* leaves `n/2`, but the algorithm halves repeatedly, and it is the repetition that collapses a million down to twenty. ## The mental model to carry forward Generalize away from the specific loop: binary search is a **search-space-shrinking** procedure. You hold a set of possibilities, you buy information with each probe, and a well-chosen probe eliminates a constant *fraction* of what remains rather than a constant *number*. Any time you can arrange a question whose answer eliminates half of the possibilities, the number of questions you need is logarithmic — that is the transferable idea, and the sorted-range loop is only its most familiar instance.