Here is a binary search that works on arrays of 1,000 elements. It works on 100. It works on 10.

But on [3, 5], searching for 5, it runs forever. No crash, no wrong answer — it just hangs.

The code uses lo = mid when the element is too small. That sounds reasonable — hi = mid works fine in other templates. Why would lo = mid be any different?

Something about lo = mid is asymmetric, and it only shows up when the array is tiny. Specifically, when only two elements remain. That is a clue worth holding onto.

This is one of the most dangerous binary search bugs because it is invisible to normal testing. On an array of 1,000 elements, the 2-element case only arises as the very last shrink before convergence — and in most cases, the search finds the target before getting there. You could write 500 test cases and never trigger the infinite loop. Then it ships to production, and one specific query hangs the server.

Think about what happens when lo = 0 and hi = 1. What is Math.floor((0 + 1) / 2)?

Pick the branch that makes progress:

Step through the binary search one iteration at a time. At each step, predict what happens to lo, hi, and mid.

Watch carefully — you will feel the moment things go wrong. The state will look almost identical from one iteration to the next, and that sameness IS the bug.

function search(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;     // BUG HERE

    else hi = mid - 1;

  }

  return arr[lo] === target ? lo : -1;

}

The key insight emerges from the arithmetic. When lo = 0 and hi = 1:

mid = Math.floor((0 + 1) / 2)  // mid = 0

// arr[0] = 3 < 5 (target), so:

lo = mid  // lo = 0 — same as before!

Floor division of two adjacent integers always produces the smaller one. So mid === lo, and lo = mid is a no-op. The interval was [0, 1] before the iteration and [0, 1] after. Nothing changed.

But hi = mid would have set hi = 0, shrinking the interval to [0, 0]. The asymmetry is not in the logic — it is in the arithmetic of floor division. Floor rounds down, which means mid is biased toward lo. That makes lo = mid dangerous and hi = mid safe.

You discovered the asymmetry yourself: hi = mid always shrinks the interval because floor division guarantees mid < hi. But lo = mid does NOT always shrink it, because floor division can produce mid = lo.

The critical case is the 2-element interval: hi = lo + 1. Floor of (lo + hi) / 2 is lo — so lo = mid is a no-op. The interval never shrinks. The loop never exits.

You tested two fixes:

Ceiling division — Math.ceil guarantees mid > lo when hi > lo, so lo = mid always makes progress. This is a surgical fix for the specific bug.

// Fix A: ceil division when using lo = mid

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

// Now mid > lo is guaranteed, so lo = mid always advances

The lo + 1 < hi template — by exiting when only 2 elements remain, the dangerous case never arises. This is a structural fix that sidesteps the problem entirely.

// Fix B: open-interval template

while (lo + 1 < hi) {

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

  // mid is always strictly between lo and hi

  // so both lo = mid and hi = mid are safe

}

// After loop: check arr[lo] and arr[hi] separately

The decision rule you built is mechanical, not intuitive: see lo = mid in your code? Use ceiling division. See hi = mid? Floor is safe. Not sure? Use lo + 1 < hi. This rule is a formal consequence of the loop variant — the quantity that must strictly decrease each iteration. Every correct binary search has one. Every infinite loop is a violation.

Here is a trick that catches this bug class instantly: the 2-element litmus test. Before submitting any binary search, mentally run it on an array of exactly 2 elements, with the target as the second element. Set lo = 0, hi = 1. Compute mid. Trace one full iteration. If lo and hi are unchanged after the iteration — you have an infinite loop. This single test case catches every lo = mid infinite loop because the 2-element interval is the only case where floor division produces mid === lo.

// The 2-element litmus test:

// lo = 0, hi = 1

// mid = Math.floor((0 + 1) / 2) = 0

//

// If your "too small" branch does lo = mid:

//   lo = 0 → unchanged! INFINITE LOOP.

//

// If it does lo = mid + 1:

//   lo = 1 → progress! Safe.

//

// If your loop condition is lo + 1 < hi:

//   0 + 1 < 1 is false → exits before the problem. Safe.

This litmus test works because the 2-element case is the minimal reproducer for every floor-division infinite loop. It is the binary search equivalent of testing a sorting algorithm on [2, 1] — the smallest input that exercises the critical path.

The bug shows up in LC 35 (Search Insert Position), LC 278 (First Bad Version), and any problem where you write lo = mid in any branch. In contest environments where runtime limits are tight, an infinite loop on one test case means TLE on the entire submission. The 2-element litmus test takes 10 seconds and catches it every time.