Search Space Reduction (Binary Search Principle)¶

When a monotonic property divides a search space, each probe eliminates a constant fraction of candidates, achieving logarithmic queries regardless of space size.

Tension Addressed¶

Time vs. Space (prerequisite: sorted structure trades write time for read time)

Recognizable As¶

Any situation where one comparison halves remaining possibilities; requires ordered/monotonic structure; mid-point selection.

Canonical Sources¶

Knuth, The Art of Computer Programming Vol. 3, 1973; Bentley, "Programming Pearls: Writing Correct Programs," CACM, 1983

Transfers To¶

Database indexing (B-trees), git bisect, numerical methods (bisection), parameter tuning, game theory (20 questions)

The concept generalizes beyond arrays: binary search on answer (searching the output space) solves optimization problems where feasibility is monotonic.

Sub-concepts: - Invariant maintenance: The property "answer lies in [lo, hi]" must remain true across iterations - Interpolation search: When distribution is known, probe position can be estimated for expected O(log log n)