Binary search on the answer: why the predicate must be monotonic

The problem

Most students meet binary search as "the trick for sorted arrays." That is true, but sortedness is not the reason binary search works, and treating it as the reason breaks once problems stop handing you a sorted array directly. "Find the smallest value of $x$ satisfying some condition" problems are an example: no array is sorted, because there is no array at all.

The idea

Binary search needs a predicate $P(i)$ over index $i$ that is monotonic: false for a while, then true for the rest. $P(0), P(1), \dots, P(n-1)$ looks like $F, F, \dots, F, T, T, \dots, T$ with exactly one flip. Sortedness is the most common way that condition shows up. For "first index with $a_i \ge \text{target}$," the predicate $P(i) := a_i \ge \text{target}$ is monotonic precisely because the array is sorted. But plenty of monotonic predicates come from unsorted data, such as "smallest speed that finishes the race in time" or "smallest budget that satisfies every constraint," and binary search applies to all of them the same way.

The array below is sorted so the predicate is easy to see. Watch what the search tracks: the place where the predicate flips.

Full proof

Claim. If $P$ is monotonic over $\{0, \dots, n-1\}$, the loop invariant "the answer lies in $[lo, hi]$" holds at every step, and the loop terminates with the correct answer (or no answer, if $P$ is never true).

Invariant. At the start of every iteration, no index has been ruled out incorrectly: the first index where $P$ is true, if one exists, lies in $[lo, hi]$.

Base case. Initially $lo = 0$, $hi = n-1$, so the invariant holds trivially: the first true index, if any, is within $[0, n-1]$.

Inductive step. Let $mid = \lfloor (lo+hi)/2 \rfloor$.

• If $P(mid)$ is true: because $P$ is monotonic, every index $\ge mid$ is also true, so $mid$ is a valid candidate and the first true index is either $mid$ itself or something smaller. Recording $mid$ as the best answer so far and setting $hi = mid - 1$ preserves the invariant.
• If $P(mid)$ is false: monotonicity means every index $\le mid$ is also false, so the first true index (if any) must be strictly greater than $mid$. Setting $lo = mid + 1$ preserves the invariant.

Termination. Each iteration strictly shrinks $hi - lo$, so the loop ends in $O(\log n)$ steps. When $lo > hi$, the invariant's search window is empty, and the best candidate recorded along the way is exactly the first index where $P$ is true. $\blacksquare$

Where it breaks in practice. The error this editorial is filed under, assuming sortedness instead of monotonicity, shows up when someone binary searches over a value that looks array-like (a range of possible answers) without checking that the predicate is monotonic over that range. A predicate that is true, false, true is not safe to binary search, even if the "array" it is defined over happens to be sorted numbers.