Here's a binary search that passes every test you throw at it — almost. On [1, 3, 5, 7, 9] searching for 4, it runs forever.

No crash. No wrong answer. It just... never stops.

The code looks right. The comparisons are correct. The midpoint calculation is fine. You could stare at it for an hour and not see the problem. This is the most insidious class of bug in binary search: the code that almost works, passes 99% of test cases, and then silently hangs in production on one specific input.

Think about what makes 4 special. It does not appear in the array. The search has to figure out that 4 is missing — but somewhere in that process, it gets trapped. Every search for a present element converges fine because the match branch returns early. The bug only surfaces when the search has to exhaust the entire space — and that only happens when the target is absent.

This is the class of bug that makes binary search infamous. It is not a logic error in the usual sense — the comparisons are right, the midpoint is right, the branching is right. The error is structural: a mismatch between how the loop decides to keep going and how the updates make progress. Understanding that distinction is the key to writing correct binary search every time.

Tap “Step again” and watch what happens. Or rather, what does not happen:

Can you figure out where it gets stuck?

Step through the loop iteration by iteration. At each step, predict what happens next — then see whether you're right.

Something will go wrong. Your job is to feel exactly when and exactly why.

function lowerBound(arr: number[], target: number): number {

  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] < target) lo = mid + 1;

    else hi = mid;  // BUG: lo <= hi with hi = mid → infinite loop

  }

  return lo;

}

The interaction above walks through the same buggy search step by step. Notice the values of lo, hi, and mid at each iteration. When lo and hi stop changing, the loop has nowhere to go — but the exit condition lo <= hi is still satisfied.

That is the core tension: the condition says “keep going,” but the pointers say “there's nowhere left to go.” This is not a logic error in the comparisons. It is a structural mismatch between the loop condition and the update rules.

Here is the buggy code for reference:

function lowerBound(arr: number[], target: number): number {

  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] < target) lo = mid + 1;

    else hi = mid;  // BUG: when lo === hi, hi = mid is a no-op

  }

  return lo;

}

The problem lives on line 6. When lo === hi === mid, setting hi = mid changes nothing. But lo <= hi is still true. The loop condition never becomes false, so the loop never exits.

You just did something most engineers skip: you named the two contracts a loop must keep, then used them to find a bug that testing alone could never isolate.

The contract you called safety — target is in arr[lo..hi] — guards correctness. Every update to lo or hi must preserve it, or the search silently skips the answer.

The contract you called progress — the search space shrinks by at least 1 each iteration — guarantees termination. You saw what happens when hi = mid and lo = hi = mid: progress dies and the loop spins forever.

These two contracts work as a team. Safety without progress gives you a correct loop that never finishes. Progress without safety gives you a loop that finishes fast with the wrong answer. You need both, and you need to verify both separately when debugging.

The fix wasn't a random tweak. You changed lo <= hi to lo < hi — one character — and the loop exited when it converged to a single element. That fix was derived from the contracts you built. No guessing, no edge-case fiddling.

Here is the corrected version:

function lowerBound(arr: number[], target: number): number {

  let lo = 0, hi = arr.length;   // hi is now exclusive

  while (lo < hi) {               // exits when lo === hi

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] < target) lo = mid + 1;

    else hi = mid;               // safe: lo < hi guarantees mid < hi

  }

  return lo;

}

With lo < hi, when the interval shrinks to a single element (lo === hi), the loop exits immediately. The hi = mid update is now always safe because mid < hi is guaranteed by floor division when lo < hi.

These contracts have a name in CS: loop invariants. Every correct binary search keeps two — safety and progress — and every binary search bug is a violation of one or both.

Here is how to apply them mechanically. For any binary search you write, ask two questions:

Safety check: "After each update, is the target still in arr[lo..hi]?" Trace through each branch. If arr[mid] < target, then the target must be at index mid + 1 or higher. So lo = mid + 1 preserves safety. If arr[mid] >= target, then the target could be at mid or earlier. So hi = mid preserves safety — but hi = mid - 1 does not, because mid itself might be the answer.

Progress check: "Does hi - lo strictly decrease each iteration?" For lo = mid + 1: since mid >= lo, setting lo = mid + 1 always increases lo, so hi - lo decreases. For hi = mid: since mid < hi (guaranteed by floor division when lo < hi), setting hi = mid always decreases hi. Both branches make progress. The contract holds.

// Safety:  target ∈ arr[lo..hi] is preserved by every update

// Progress: (hi - lo) decreases by ≥ 1 every iteration

// Together: the loop terminates AND the answer is at arr[lo]

When you encounter a binary search bug in the wild — whether in LC 704 (Binary Search), LC 35 (Search Insert Position), or a custom search in your own codebase — do not guess at fixes. Write the two invariants. Check each branch against each invariant. The one that fails points directly at the bug. The fix is the update rule that makes both invariants hold simultaneously. No intuition required, no edge-case testing — just contracts.