What property, more general than sortedness, does binary search actually require?

## Sortedness is a special case, not the requirement Most people learn binary search as "the algorithm for sorted arrays", and that framing hides the actual precondition. Halving is sound whenever one test at the midpoint reliably tells you which half of the range contains the boundary you are looking for. Formally: there must exist a predicate `pred(i)` over the index range that is **monotone** — once it turns true it stays true. ``` pred: false false false false true true true index: 0 1 2 3 4 5 6 ^ the boundary ``` Given that shape, evaluating `pred(mid)` is decisive. True means the boundary is at `mid` or below it, so discard everything above. False means it is strictly above `mid`, so discard everything at `mid` and below. Either way half the range is gone, and after about `log2 n` steps one index remains: the first true. Now look at the classic case through that lens. Over a range ordered ascending, the predicate `a[i] >= target` is false for every position before the target's place and true from there onward — monotone, precisely *because* the range is ordered. Sortedness is not the precondition; it is the most common way of manufacturing the precondition. ## Why the distinction earns its keep Three things become clear once you say "monotone predicate" instead of "sorted array". **It explains the failures.** Data ordered by one key and probed by another is not sorted in any sense the predicate can use: `pred` flips back and forth, so the midpoint test is not decisive and the halving discards a region that may contain the answer. "Almost sorted" fails for the same reason — a predicate that is false, true, false, true near the boundary has no single crossing to find, and the search converges confidently on the wrong index. **It widens the technique correctly.** Any question of the form "what is the smallest parameter value at which this check succeeds, where succeeding at one value implies succeeding at every larger one" is a binary search, even though nothing is stored in order anywhere. The monotonicity has to be *argued*, not assumed — and that argument is exactly what an interviewer is probing when they ask why binary search applies. **It clarifies what to prove.** When you claim binary search is applicable, the thing to justify is the monotone shape of your predicate over the range you are halving. If you cannot state the predicate, you cannot state the precondition, and the applicability claim is a guess. ## The other requirement: reaching the midpoint Monotonicity makes halving *correct*; it does not make it *fast*. The `O(log n)` bound also assumes you can evaluate the midpoint without walking to it. Over an indexed range that is a single address computation. Over a structure you can only traverse one link at a time, reaching the midpoint costs a walk proportional to the distance, and the halving does not buy you anything — you end up doing linear work per step. This is why the technique is described as needing **random access plus an ordered (or monotone) domain**: drop either half of that and either correctness or the logarithmic bound goes away. If evaluating the predicate itself is expensive — a computation, a probe of something remote — the cost model changes shape again. The count of evaluations is still about `log2 n`, which is usually the point: minimising an expensive check is often the whole reason for halving in the first place. ## The invariant to state out loud The boundary-search formulation is worth memorising because it is the one that generalises and the one with the fewest off-by-one traps. Maintain `lo` and `hi` such that: - `pred(i)` is false for every `i < lo`; - `pred(i)` is true for every `i >= hi`; - the boundary lies in `[lo, hi]`. Initialise `lo = 0`, `hi = n` (one past the last index, representing "no true index exists"), and loop while `lo < hi`. Each step either raises `lo` past a false midpoint or lowers `hi` to a true midpoint, so the range strictly shrinks and the invariant is preserved. On exit `lo == hi` is the first true index, or `n` if there is none. Being able to state that invariant — and to say which half is discarded and why — is a much better answer to "how does binary search work" than reciting the comparison version, because it names the property the algorithm actually depends on.