skip to content

Why does a binary search loop that rounds mid down and then sets lo = mid hang on a two-element range?

level: middleimportance: must knowfreq 62%

answer

  1. look at the state just before it hangs
  2. two candidates left, rounding downward
  3. where does the midpoint land then
  4. does every branch shrink the range?
  5. rounding and shrink must be a matched pair

basics

~20 s

Rounding down makes the midpoint equal the lower bound whenever two candidates remain, so assigning it back to the lower bound leaves the range unchanged and the loop repeats that state forever. Every branch must strictly shrink the range.

solid answer

~50 s

With a downward-rounded midpoint and `lo < hi`, the midpoint always satisfies `lo <= mid < hi` — it can equal `lo`, but never `hi`. That asymmetry decides which shrink steps are legal. Setting `hi = mid` is fine, because `mid` is strictly below `hi`, so the range really shrinks. Setting `lo = mid` is not: on a two-candidate range the midpoint *is* `lo`, the assignment is a no-op, and the loop revisits an identical state forever. The fix is to pair the rounding with the shrink: downward rounding goes with `hi = mid` and `lo = mid + 1`; a branch that genuinely needs to keep the midpoint as the new lower bound must round **up**, `mid = lo + (hi - lo + 1) / 2`, paired with `hi = mid - 1`. The general rule is a termination argument: `hi - lo` must strictly decrease on every branch.

code

pseudocode · 10 lines
pseudocode
// find the leftmost position where ready(a[i]) holds
lo = 0
hi = length(a) - 1
while lo < hi:
    mid = lo + (hi - lo) / 2     // rounds down
    if ready(a[mid]):
        hi = mid                 // shrinks: mid < hi
    else:
        lo = mid                 // suspect: mid may equal lo
return lo

go deeper

for a junior

Be ready to trace a halving loop by hand on a range of two candidates and say what the midpoint is there. Knowing that rounding down makes the midpoint equal the lower bound is most of the answer.

for a middle

Explain the asymmetry that causes it — the midpoint is stuck to one bound and strictly inside the other — and name both matched rounding/shrink pairs rather than reciting one template.

for a senior

Show the review habit: state a decreasing measure, check it on every branch, and trace ranges of size two, one and zero. Be able to say why an iteration cap or a special case is not a fix.

for a principal

Own the tradeoff between the two loop shapes and pick one as the house form: unconditional termination with an explicit midpoint check, versus converging to a single position at the cost of a matched pair engineers must not split.

## The state that never changes Take the loop above and put it in the state `lo = 2`, `hi = 3` — two candidates left. The midpoint is `2 + (3 - 2)/2 = 2 + 0 = 2`, which is exactly `lo`. If the branch taken is the one that assigns `lo = mid`, the new `lo` is 2 and `hi` is still 3. Nothing about the machine's state has changed: same bounds, same midpoint, same branch, forever. The loop condition `lo < hi` is still true, and it will be true on every future iteration too. This is the single most common way a hand-written halving loop hangs, and it is not a typo — it is a mismatch between two decisions that must be made together. ## The asymmetry that causes it When `lo < hi` and the midpoint rounds **down**: lo <= mid < hi The left inequality can be an equality (two candidates left), the right one never can. So the midpoint is "stuck to" the lower bound and "free of" the upper bound. That single fact decides which assignments are safe: | shrink step | with a downward-rounded mid | why | | --- | --- | --- | | `hi = mid` | safe | `mid < hi`, so the upper bound strictly falls | | `lo = mid + 1` | safe | strictly above the old `lo` | | `lo = mid` | **hangs** | `mid` can equal `lo`, so nothing moves | | `hi = mid - 1` | safe but discards `mid` | fine only if `mid` cannot be the answer | Round the midpoint **up** instead — `mid = lo + (hi - lo + 1) / 2` — and the inequality flips to `lo < mid <= hi`. Now `lo = mid` is the safe assignment and `hi = mid` is the one that hangs. This is why the two working templates for a `while lo < hi` loop come as matched pairs: - **round down** with `hi = mid` / `lo = mid + 1` - **round up** with `lo = mid` / `hi = mid - 1` Mixing halves of the two pairs is the bug. Memorising one pair as a unit — rounding and shrink together — is what makes the template reliable; memorising the midpoint line alone is what produces the hang. ## Why the closed-interval form is immune The other common shape uses an inclusive upper bound and the condition `lo <= hi`, with both branches excluding the midpoint: `lo = mid + 1` or `hi = mid - 1`. Here **no** branch keeps the midpoint, so the candidate count drops by at least one every iteration regardless of rounding. Termination is unconditional; the loop ends when the range becomes empty (`lo > hi`). The price is that the midpoint must be genuinely disposable — the code has to handle a match at the midpoint separately, usually by returning from inside the loop. That trade is worth stating out loud in an interview: the `lo < hi` form converges to a single surviving position and never needs an empty-range check, but it demands a matched rounding/shrink pair. The `lo <= hi` form terminates unconditionally but must dispose of the midpoint on every path. ## The termination argument to state at the whiteboard Non-termination is not something you find by staring; you find it by naming a **measure**: a non-negative integer quantity that must strictly decrease every iteration. Here the natural measure is the number of remaining candidates, `hi - lo` (or `hi - lo + 1` for an inclusive range). Then check it once per branch: 1. Branch A: does the measure fall? By how much, at minimum? 2. Branch B: same question. 3. Can the measure reach the loop's exit condition from any reachable state? If any branch can leave the measure equal, the loop can hang — no size of test input will make that branch safe, so testing on large collections proves nothing. The failure is concentrated exactly where nobody tests: ranges of size 1 and 2. That is the practical review heuristic. When you read a halving loop in a diff, do not trace it on a hundred elements; trace it on two, then on one, then on zero. ## Things that look like fixes and are not - **An iteration cap.** Bounding the loop at some multiple of log(n) converts a hang into a wrong answer plus a mystery. The state machine is still broken. - **Changing the loop condition to `lo <= hi` without touching the shrink.** Now the same no-op branch runs with the bounds crossed differently; you can trade a hang for an out-of-range read at the midpoint. - **Adding a special case for a two-element range.** It patches the one state you happened to notice while leaving the pairing wrong; the same mismatch reappears in the next variant someone copies out of this file. The real fix is one character in the right place — `lo = mid + 1` — chosen because it restores the invariant that every branch strictly shrinks the search range.

  • Give both consistent pairings of midpoint rounding and shrink step for a loop conditioned on lo < hi.
    Round down (`mid = lo + (hi - lo) / 2`) and pair it with `hi = mid` on one branch and `lo = mid + 1` on the other. Round up (`mid = lo + (hi - lo + 1) / 2`) and pair it with `lo = mid` and `hi = mid - 1`. In each pair, the branch that keeps the midpoint is the one the rounding pushes strictly away from that bound.
  • Why can the closed-interval form with lo <= hi, lo = mid + 1 and hi = mid - 1 never hang?
    Neither branch keeps the midpoint, so the candidate count falls by at least one on every path regardless of how the midpoint rounds. The measure `hi - lo + 1` is a non-negative integer that strictly decreases, so the loop must reach the empty range and exit. The cost is that a match at the midpoint has to be handled explicitly, since both branches throw that position away.
  • How would you catch this class of bug in review without running the code?
    Name a measure — the number of remaining candidates — and check branch by branch that it strictly decreases; any branch that can leave it unchanged is a hang. Then trace the loop on ranges of size two, one and zero, which is where the rounding bias shows and where nobody's test data lives.

A ratchet with one worn tooth: most turns click forward, but on one position the pawl slips back into the same notch, and the mechanism spins without ever advancing.

saying these in an interview costs you the question

  • Believes the loop condition alone guarantees termination
  • Treats rounding up versus down as a style preference
  • Only tests on large inputs and never on two candidates
  • Fixes the hang by capping the iteration count
  • Thinks a downward-rounded midpoint can equal the upper bound

context

resolving links…