In a collapsing rightmost-occurrence search, why does a floored midpoint with lo = mid loop forever?
answer
- look at a two-element interval
- what does the midpoint compute to there
- one branch keeps mid alive
- the assignment becomes a no-op
- bias the rounding toward the assigned pointer
basics
~20 sA floored midpoint equals the low bound whenever two elements remain, so the branch that keeps the midpoint by assigning it back to the low bound makes no progress and the iteration repeats identically. Rounding the midpoint up fixes it.
solid answer
~50 sIn the collapsing shape the loop runs while `lo < hi` and one branch must keep `mid` alive as a possible answer, so it writes `lo = mid`. With a floored midpoint and `hi == lo + 1`, `mid` computes to `lo` — the assignment is a no-op, the interval never shrinks, and the loop spins. The fix is to bias the midpoint toward the pointer that gets assigned `mid`: use the ceiling, `mid = lo + (hi - lo + 1) / 2`, so `mid` is never equal to `lo` when the interval has at least two elements. The general rule is symmetric — a branch writing `hi = mid` requires the floor, a branch writing `lo = mid` requires the ceiling. The record-and-shrink shape sidesteps this entirely because every branch moves past `mid`.
code
pseudocode · 11 lines// BUG: hangs on a two-element interval
lo = 0
hi = length(a) - 1
while lo < hi:
mid = lo + (hi - lo) / 2 // floor -> mid == lo when hi == lo + 1
if a[mid] <= target:
lo = mid // keeps mid as a candidate; no progress
else:
hi = mid - 1
// fix: mid = lo + (hi - lo + 1) / 2
return logo deeper
Be ready to reason about what the midpoint evaluates to when only two elements remain. Recognising that an assignment can leave the state unchanged, and that this means the loop never ends, is the takeaway here.
Expect to be handed a mirrored loop and asked what breaks. State the rule out loud — bias the rounding toward the pointer that receives the midpoint — and show which branch keeps the midpoint alive and why that forces the choice.
Show how you would have caught it: a two-element all-duplicates case in the test table, and a review habit of checking that every branch strictly shrinks the interval. Explain why this bug passes hand-run samples and hangs on skewed production data.
Weigh terseness against a termination argument a reviewer can check in one line. Deciding that a team standardises on the shape with no load-bearing rounding, and reviews the tight variant only where it is measurably justified, is the call to own.
## Two shapes, two termination arguments Boundary searches come in two families, and the trap here belongs to only one of them. **Record and shrink** runs while `lo <= hi` and every branch moves a pointer strictly past `mid` (`lo = mid + 1` or `hi = mid - 1`). The candidate answer is stashed in a separate variable. Termination is trivial: `hi - lo` strictly decreases every iteration. **Collapse** runs while `lo < hi` and drives the two pointers together onto a single surviving index, with no separate candidate variable. To do that, the branch that believes `mid` might be the final answer must *keep* `mid` in the interval — writing `lo = mid`, not `lo = mid + 1`. That is where progress can be lost. ## The fixed point With the usual floored midpoint `mid = lo + (hi - lo) / 2`, consider the smallest interval the loop still accepts: `hi == lo + 1`, two elements. Then `hi - lo == 1`, integer division gives `0`, and `mid == lo`. If the branch taken is `lo = mid`, the state after the iteration is identical to the state before it — same `lo`, same `hi`, same comparison, same branch. The loop is a fixed point and never exits. The minimal reproducing input is therefore tiny: a two-element array in which both elements equal the target, searched for the last occurrence. The first comparison keeps the left element as a candidate and the search hangs. A single-element array does not reproduce it (the loop test `lo < hi` is false immediately), and an array where the target appears once usually does not either, because the other branch — the one that excludes `mid` — makes progress. That is what makes the bug survive casual testing: it needs duplicates *and* the right interval parity to show up, so it can pass a hand-run sample and hang on real data. ## The rule > Bias the midpoint **toward the pointer that gets assigned `mid`**. - A branch that writes `hi = mid` needs the **floor**, so that `mid < hi` whenever the interval has two or more elements; `hi` strictly decreases. - A branch that writes `lo = mid` needs the **ceiling**, `mid = lo + (hi - lo + 1) / 2`, so that `mid > lo`; `lo` strictly increases. Since a rightmost-occurrence search is the one that keeps `mid` on the low side, it is the ceiling variant. Its mirror image, the leftmost search in collapse form, keeps `mid` on the high side and needs the floor. Two searches that look like transpositions of each other need *different* midpoint rounding — which is exactly why people write the first one, mirror it mechanically, and hang. ## Writing the correct rightmost collapse loop With the ceiling in place, the loop keeps `mid` when `a[mid] <= target` (the answer is `mid` or further right) and discards it otherwise (`hi = mid - 1`). Both branches now shrink: the first because `mid > lo`, the second because `hi` drops below `mid`. When `lo == hi`, that single index is the largest index whose value does not exceed the target, so one final equality check tells you whether it is a real occurrence or the target is absent. ## Why the other shape avoids all of this The record-and-shrink form never needs a rounding decision, because it never keeps `mid` in the interval — it keeps the *value* of `mid` in a variable instead. Preserving information in a variable rather than in the interval bounds is what makes its termination one line long. If you are writing a boundary search under interview pressure, or writing one that other people will maintain, that is the shape to prefer; the collapse form is tighter and appears widely, so you should be able to read it and spot the rounding, but it buys elegance with a load-bearing subtlety. ## A related midpoint detail The form `lo + (hi - lo) / 2` rather than `(lo + hi) / 2` is about overflow of the index sum on very large arrays in fixed-width arithmetic, not about rounding — both floor. The ceiling variant keeps the same overflow-safe structure, adding one before dividing: `lo + (hi - lo + 1) / 2`. Do not conflate the two fixes; they solve unrelated problems, and quoting the overflow-safe form as the answer to a hang is a common wrong turn. ## Checklist for reviewing a collapse-form search 1. Which branch keeps `mid`? That decides the rounding. 2. Does the other branch move strictly past `mid`? 3. Does the loop test use `<` (collapse) or `<=` (record-and-shrink), matching the shape? 4. Is there a post-loop check for the target actually being present? 5. Is there a test with a two-element array of identical keys?
- What is the smallest input that reproduces the hang?A two-element array whose values both equal the target, searched for the last occurrence. The loop test passes because `lo < hi`, the floored midpoint is the low index, the comparison takes the keep-mid branch, and the state is unchanged. A one-element array cannot reproduce it — the loop never runs — and an array with a single occurrence usually takes the other branch, which does make progress. That narrowness is why it survives casual testing.
- Why doesn't the record-and-shrink form need any of this rounding care?Because it never keeps the midpoint inside the interval. It saves the midpoint's value in a candidate variable and then moves the pointer strictly past it, so `hi - lo` decreases in every branch regardless of rounding. Information is preserved in a variable instead of in the bounds, which makes the termination argument one line and removes the whole class of midpoint-bias bugs.
- Is switching to an overflow-safe midpoint a fix for this?No — these are unrelated problems. Computing the midpoint as low plus half the span rather than as half the sum avoids overflowing the index arithmetic on very large arrays, but it still rounds down. The hang is caused by the rounding direction, not by the arithmetic form, and is fixed by adding one before halving the span. Quoting the overflow fix here is a common wrong turn.
Two people closing in from opposite ends of a corridor: if one of them is allowed to step onto the tile they already occupy, they can stand there forever without ever meeting.
saying these in an interview costs you the question
- Blames duplicates rather than the midpoint rounding
- Mirrors the leftmost loop and keeps the floored midpoint
- Offers the overflow-safe midpoint as the fix for a hang
- Adds an iteration counter or bail-out instead of fixing progress
- Never tests a two-element array of identical keys