Binary Search Invariants

Binary search becomes easier when the loop is written around a statement that remains true.

The invariant

Keep two boundaries:

• lo is known to be false.
• hi is known to be true.

Then shrink the interval until the first true position is isolated.

function firstTrue(n: number, ok: (index: number) => boolean) {
  let lo = -1;
  let hi = n;
 
  while (hi - lo > 1) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (ok(mid)) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
 
  return hi;
}

Why it works

The loop preserves the meaning of both boundaries. Once there is no integer between them, hi is the answer.

Common mistakes

The usual mistakes are mixing inclusive and exclusive boundaries, updating the wrong side, or choosing a midpoint formula that overflows in fixed-width integer languages.