Why do binary search implementations compute mid as lo + (hi - lo) / 2 instead of (lo + hi) / 2?
answer
- both forms agree in exact arithmetic
- think about very large index values
- the sum is the problem, not the quotient
- fixed-width signed addition wraps negative
- subtract before you add
basics
~20 sAdding lo and hi can overflow a fixed-width signed integer once indices grow large, wrapping negative and yielding an out-of-range midpoint. Computing lo + (hi - lo) / 2 keeps every intermediate value inside the valid index range.
solid answer
~50 sThe two expressions are identical in exact arithmetic, but not in fixed-width signed arithmetic. With 32-bit signed indices, `lo + hi` can exceed the largest representable value once the two sum past 2^31, and the sum wraps to a negative number; halving that gives a negative `mid`, and the next indexed read is out of range. `hi - lo` cannot overflow while `lo <= hi` and both are non-negative — it is at most the largest valid index — so `lo + (hi - lo) / 2` stays in range for every reachable state. This is not theoretical: the naive form sat unnoticed inside widely used built-in search routines for years, because nobody tested collections large enough to reach the wrap point. Keep the safe form even where indices are wide enough that the bound is unreachable; it costs nothing and survives being copied into a narrower context.
go deeper
Be ready to state the safe midpoint expression and say in one sentence why it is safe: the sum of two large indices can wrap negative, while the difference cannot. Write the safe form by reflex.
Explain the arithmetic underneath: fixed-width two's-complement addition wraps silently, and the loop's own premise that lo is at most hi is what bounds the difference. Know roughly what index size triggers it.
Show how you would spot this in review and decide whether it matters here: what width are the indices, could this code be reused in a narrower context, and is the failure a raised error or a silent bad read?
Own the general lesson rather than the one-liner: name which intermediate value an expression forces the machine to hold, and set a house rule so the safe form is the default instead of a fact each engineer has to remember.
## The two expressions are the same, until they are not In ordinary mathematics `(lo + hi) / 2` and `lo + (hi - lo) / 2` are the same number. Expand the second: `lo + (hi - lo)/2 = (2*lo + hi - lo)/2 = (lo + hi)/2`. With floor division on non-negative values the two agree exactly, so the rewrite is not a rounding trick — it changes nothing about which element is chosen. What it changes is the size of the largest **intermediate** value the machine has to hold. ## Fixed-width signed arithmetic Most languages represent an index as a fixed-width signed integer: a fixed number of bits, one of which encodes sign, giving a range of roughly -2^(w-1) to 2^(w-1) - 1 for width w. Arithmetic that leaves this range does not grow a bigger number; it wraps around (two's complement) — the result is the true value modulo 2^w, reinterpreted as signed. Adding two large positive values therefore yields a **negative** result, silently, with no error and no diagnostic. Now trace the naive midpoint on a very large collection with 32-bit indices, where the largest representable value is 2^31 - 1 (about 2.147 billion). Suppose the search has narrowed to `lo = 1_500_000_000`, `hi = 1_800_000_000`. Their true sum is 3.3 billion, which is past the maximum. The stored sum wraps to a negative number near -0.99 billion; dividing by two keeps it negative; the loop then reads at a negative index. Depending on the runtime that is a thrown range error, a segmentation fault, or — worst of all — a silent read of unrelated memory. The safe form never builds that sum. Given the loop's own premise `lo <= hi`, the difference `hi - lo` is non-negative and at most `hi`, which is a valid index by construction. Halving it makes it smaller still, and adding it back to `lo` produces a value between `lo` and `hi` inclusive. Every intermediate is bounded by a value the type already holds. ## Why it stayed hidden for so long The bug needs about a billion elements before it can fire, and for most of computing history nobody allocated a contiguous structure that large. That is exactly what makes it a famous review lesson rather than a famous outage: it lived inside heavily used, heavily reviewed built-in search and sort routines for years, was proved correct on paper under the wrong arithmetic model, and only surfaced when memory sizes caught up. A defect that requires unusual scale to trigger is not a rare defect — it is a defect with a delayed fuse. **Where the arithmetic model differs across ecosystems.** This hazard is a property of the number type, not of the algorithm. Languages such as C, C++, Java and Go use fixed-width machine integers, so the wrap is real (in C and C++ signed overflow is undefined behaviour, which is worse than wrapping — the compiler may assume it cannot happen and optimise accordingly). Rust wraps in release builds but panics in debug builds by default. Python and Ruby promote integers to arbitrary precision, so the sum simply grows and the bug cannot occur there at all. Same five lines of pseudocode, three different failure behaviours — a good reminder that a complexity or correctness argument silently assumes an arithmetic model. ## Alternatives, and their fine print - **Unsigned/logical right shift of the sum.** Where indices are non-negative and the wrapped sum still holds the correct bit pattern, reinterpreting it as unsigned and shifting right by one recovers the true midpoint. It is correct, and used in production code, but it leans on wraparound semantics that are not guaranteed everywhere and it breaks if the range can be negative. - **A wider intermediate type.** Promote to a wider integer, compute, narrow back. Correct, but it costs a conversion and only moves the ceiling. - **`lo + (hi - lo) / 2`.** No reliance on wrap semantics, no width games, reads as "start at lo and step half the remaining distance". This is why it is the house form. One caveat worth stating in an interview: the safe form is safe **because the loop guarantees `lo <= hi` and both are non-negative array indices**. If you reuse the pattern over a general signed range — binary searching an answer space that may include large negative values — then `hi - lo` is the expression that can overflow instead. In that setting you need a wider type or a formula built for signed ranges. The lesson generalises better than the one-liner does: know which intermediate is the largest one your expression forces the machine to hold. ## What a reviewer should do with this Seeing `(lo + hi) / 2` in a diff is not automatically a bug — on 64-bit indices the wrap point is unreachable for any collection that fits in memory. Treat it instead as a signal to ask two questions: what width are these indices, and could this code be copied into a narrower context later? The safe form costs one extra token and removes the question entirely, which is why most style guides simply mandate it.
- How large does the collection have to get before the naive midpoint actually breaks?With 32-bit signed indices the sum overflows once `lo + hi` passes 2^31 - 1, so roughly a billion elements with both bounds well inside the array. With 64-bit indices the wrap point is around 2^63, unreachable for anything that fits in memory — which is precisely why the bug stayed latent in reviewed library code for years rather than being caught on day one.
- Is shifting the sum right by one bit an acceptable alternative fix?It works when both indices are non-negative and the platform wraps on overflow: the wrapped sum still carries the correct bit pattern, so a logical (unsigned) right shift recovers the true midpoint. But it depends on wraparound semantics and on non-negativity, and it silently breaks if the range can go negative. The subtract-first form needs no such assumptions, which is why it is preferred.
- Does the same risk exist if lo and hi can both be negative, as when binary searching an answer range?Yes, and it flips. With a large positive `hi` and a large negative `lo`, it is `hi - lo` that overflows while `lo + hi` is fine. Neither form is universally safe over a full signed range; you need a wider intermediate type or a formula written for signed bounds. The takeaway is to know which intermediate your expression forces the machine to hold.
Two mailboxes on one street: instead of adding both house numbers (a total that can run past the end of the street) and halving it, you stand at the first and walk half the distance to the second. You never leave the street.
saying these in an interview costs you the question
- Says both forms are identical because the algebra is identical
- Claims the compiler or runtime prevents integer overflow
- Thinks the bug can appear on ordinary small collections
- Blames the division or the rounding rather than the addition
- Assumes an error is always raised when a value wraps