March 25, 2026 · 6 min read

Binary Search Template I Reuse for First True

A reusable binary search template for boundary problems, with loop invariants and off-by-one safety tips.

Algorithms

Source

Boundary Search Pattern Notes

Open original reference

Complexity

Time: O(log n)

Space: O(1)

Problem in My Words

For a monotonic predicate, find the smallest index where condition becomes true.

Approach

Use binary search with invariant that answer stays in [left, right]. Move right on true, otherwise move left to mid+1.

Key Points

Use left + (right-left)/2 style midpoint.
Keep answer range invariant explicit.
Use left < right loop for first-true boundary search.

Implementation

function firstTrue(n: number, predicate: (x: number) => boolean): number {
  let left = 0;
  let right = n - 1;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (predicate(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }

  return left;
}