Most people learn binary search as "find a number in a sorted array". That framing is why it feels fragile. Off-by-one errors, infinite loops, and the endless debate about < versus <= all come from memorizing code instead of understanding the rule underneath.

The rule underneath

Binary search works whenever you have a monotonic condition: a yes/no question that is false for a while and then true forever after.

index:     0     1     2     3     4     5
is >= 7?   no    no    no    yes   yes   yes
                             ^ first true

Your job is to find the boundary. The array is just one way to ask the question.

One template

// Returns the first index in [lo, hi) where ok(index) is true, or hi if none.
function firstTrue(lo: number, hi: number, ok: (i: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (ok(mid)) hi = mid;      // mid might be the answer; keep it
    else lo = mid + 1;          // mid is definitely not the answer
  }
  return lo;
}

Two invariants make it correct:

  1. Everything before lo is known to be false.
  2. Everything at or after hi is known to be true.

The loop shrinks the unknown window until it is empty, and lo is the boundary.

The same template, different questions

Problem Condition ok(x)
Lower bound of a target nums[x] >= target
First bad version isBadVersion(x)
Minimum eating speed "can finish all piles at speed x within h hours"
Ship packages in D days "capacity x ships everything in D days"
Square root (integer) x * x > n, then step back one

The last three are the interesting ones. There is no array at all. You binary search over the answer space and ask whether a candidate answer is feasible.

Example: minimum eating speed

function minEatingSpeed(piles: number[], h: number): number {
  const hoursAt = (speed: number) => piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0);
  return firstTrue(1, Math.max(...piles) + 1, (speed) => hoursAt(speed) <= h);
}

Faster speeds always need fewer hours, so the condition is monotonic. That single observation is the whole solution.

How to spot it in an interview

  • The input is sorted, or the answer lives in a numeric range.
  • You can check a candidate answer faster than you can compute the answer directly.
  • The question says "minimum X such that" or "maximum X such that".

If you can phrase the problem as "find the first value where this becomes true", you already know how to solve it.

Want to watch the boundary move step by step? Try the interactive binary search lab.