Level 2 · 30 min

Binary Search: The Invariant Formula

Binary search is a proof technique disguised as a loop. The hard part is not computing mid; it is defining an invariant that remains true after every branch.

Search over monotonic truth

Binary search works when the answer space is ordered and the predicate is monotonic: false false false true true true, or the reverse. That includes sorted arrays, minimum feasible capacity, first bad version, and threshold tuning.

Intervals are contracts

Pick closed intervals or half-open intervals and stick to the contract. Half-open ranges such as left inclusive, right exclusive reduce off-by-one bugs because the empty range is left == right. Every update must shrink the range.

Midpoint and termination

Use mid = left + floor((right - left) / 2) to avoid overflow in languages with fixed-width integers. Termination follows from shrinking the interval. After the loop, interpret left according to the invariant, not by intuition.

Key Takeaways

Binary search requires a monotonic predicate, not necessarily an array.
The interval invariant tells you the loop condition and the final answer.
Every branch must shrink the interval or the loop can hang on two elements.

Code example

function firstTrue(low, high, predicate):
  left = low
  right = high + 1
  while left < right:
    mid = left + floor((right - left) / 2)
    if predicate(mid):
      right = mid
    else:
      left = mid + 1
  return left