Skip to content

GOOGLE 2025-01-11 Tier 1

Read original ↗

Google Research — Nearly All Binary Searches and Mergesorts are Broken (2006)

Summary

Joshua Bloch's 2006 Google Research blog post — republished on the Google Research blog 2025-01-11 (HN 164) — reports that the standard textbook binary search, including the version Bloch himself wrote for the JDK's java.util.Arrays.binarySearch and the version Jon Bentley "proved correct" in Programming Pearls (Addison-Wesley 1986, 2nd ed. 2000, Chapter 5), contains an integer-overflow bug that lay dormant for roughly two decades. The offending line is int mid = (low + high) / 2; — the sum low + high overflows the signed 32-bit int range (2^31 − 1) once the array length reaches 2^30 (≈1 billion) elements, producing a negative mid. In C, this reads out of bounds with undefined behaviour; in Java, it throws ArrayIndexOutOfBoundsException. The bug generalises to mergesort and every other divide-and-conquer algorithm that averages two indices the same way. Fixes: mid = low + ((high - low) / 2) or, equivalently and faster, mid = (low + high) >>> 1 (Java's logical / unsigned right shift); in C/C++, ((unsigned int)low + (unsigned int)high) >> 1 (a 2008 update in the post notes the original C fix relied on signed-overflow behaviour that ISO/IEC 9899 / C99 explicitly leaves undefined, so the unsigned cast is the only standards-conformant form). Bloch's meta-lesson is epistemic humility — proof, testing, formal methods, code review, static analysis, peer review are each insufficient on their own; bugs can survive half a century despite every technique in the toolbox. "We must program carefully, defensively, and remain ever vigilant."

Key takeaways

  1. The bug is in the index-midpoint computation, not the algorithm. int mid = (low + high) / 2 appears to compute the average of two non-negative ints, and does — until low + high overflows 2^31 − 1. Once the sum overflows, it wraps to a negative value; integer division by 2 preserves the sign; a[mid] indexes at a negative offset. The algorithm itself is correct; the arithmetic is not (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006). Canonical wiki instance of concepts/integer-overflow.

  2. The bug was dormant for ~20 years because nobody had arrays large enough to trigger it. Bentley's Programming Pearls was written in the 1980s; int was 32-bit; RAM was measured in megabytes; arrays of 2^30 elements were "inconceivable". By 2006 — and routinely at Google — arrays crossed that threshold. The bug didn't appear; the precondition did. Wiki lesson: correctness-under-all-inputs is not the same as correctness-under-inputs-we-tested — a foundational concepts/program-correctness framing (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006).

  3. The same bug afflicts mergesort, quicksort partitioning, and every divide-and-conquer that averages two indices. Bloch: "The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up." A single arithmetic shape ((low + high) / 2) propagates through an entire family of textbook algorithms. Wiki instance of patterns/safe-midpoint-computation (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006).

  4. Fix A: mid = low + ((high - low) / 2) — avoid the overflow by never forming the sum. Because low ≤ high, the difference high - low cannot overflow and cannot go negative; adding half of it to low lands in the same range. Language-agnostic; the safe shape for any ordered-integer midpoint computation.

  5. Fix B: mid = (low + high) >>> 1 — Java's logical (unsigned) right shift. Bloch notes this is "probably faster, and arguably as clear": >>> treats the 32-bit pattern as unsigned before shifting, so the overflowed high-bit-set pattern shifts in a zero from the left instead of sign-extending. The arithmetic-overflow wrap-around is undone by the shift, yielding the correct midpoint. First wiki instance of concepts/unsigned-right-shift — a language-level primitive (Java's >>>, C/C++ cast-to-unsigned then >>) that is load-bearing precisely in the divide-and-conquer / bit-manipulation hot paths where this bug lives.

  6. C/C++ equivalent: mid = ((unsigned int)low + (unsigned int)high) >> 1 — and the 2008 update is the interesting part. The original post proposed a signed-addition variant for C; a 2008 update from Antoine Trux (Nokia Research) flagged that ISO/IEC 9899 (C99, §6.5) and the C++ standard both leave signed-integer overflow undefined, so any code that "works because int overflow wraps" is non-portable and non-standards-conformant. The unsigned cast is the only form that is guaranteed-correct per the standards. Wiki lesson: what happens to work on your target and what the language specification guarantees are different; defensive portable code tracks the spec, not the compiler (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006). This is the same class of hazard that concepts/memory-safety addresses in C/C++ — the language's undefined-behaviour surface is the bug substrate.

  7. Proof, test, formal methods, code review, static analysis — each alone is insufficient. Bentley's binary search was proved correct and tested in Programming Pearls. Bloch's JDK version went through Sun's code-review and static-analysis pipeline. The JDK version specifically lay in wait for nine years before a real user hit it. The meta-lesson is that a multi-technique guardrail is necessary but not sufficient: "they will always be with us" (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006). Sister wiki thesis: concepts/lightweight-formal-verification (industrialize multiple techniques, don't rely on any one) and Dropbox's patterns/property-based-testing (test the invariants not the examples).

  8. Invariants are the thing. Bloch opens with Bentley's CMU Algorithms lecture — "the key lesson was to carefully consider the invariants in your programs" — and the bug is in precisely the line whose invariant was "mid is the average of low and high, truncated down". The assertion is true in the mathematical integers and false in the int machine representation. Canonical wiki instance of patterns/invariant-driven-programming — the discipline of naming the invariants a piece of code relies on, writing them down, and checking them against the substrate semantics (signed arithmetic, floating-point rounding, lock-ordering, TCP's ordered-delivery-within-a-connection) rather than the intended semantics.

  9. You cannot test your way to certainty. "It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible." For binary search on int[], exhaustive test-space is 2^32 · 2^32 — on modern hardware you still can't cover it. The practical response is property-based testing (Dropbox's Nucleus approach), lightweight formal verification (S3's ShardStore approach), and fuzzing — all of which target the input-space-explosion problem structurally rather than enumeratively (Source: sources/2025-01-11-google-nearly-all-binary-searches-and-mergesorts-are-broken-2006).

  10. Concurrency makes the problem worse, not better. Bloch's aside: "With concurrent programs, it's even worse: You have to test for all internal states, which is, for all practical purposes, impossible." The input space for a concurrent program is inputs × interleavings, where the interleaving axis is superpolynomial in program size. Motivates Dropbox's concepts/deterministic-simulation (collapse the interleaving axis to a reproducible seed) — the concurrent analogue of the property-based response to binary search's enumerative-test-impossibility.

Systems / concepts / patterns extracted

  • systems/openjdk-arrays-binarysearch (new) — the concrete JDK implementation (java.util.Arrays.binarySearch) whose overflow bug was the real-world precipitant; carried the bug for ~9 years before user-reported.
  • systems/programming-pearls (new) — Jon Bentley's 1986 / 2000 book; wiki reference stub for the canonical proved-correct-but-wrong binary-search case.
  • concepts/integer-overflow (new) — the fundamental bug-substrate: fixed-width signed integer arithmetic can wrap around zero when sums/products exceed INT_MAX (C/C++: undefined behaviour; Java: defined two's-complement wrap).
  • concepts/program-correctness (new) — correctness-under-all-valid-inputs vs. correctness-under-inputs- we-tested; the framing the binary-search bug is a case study for.
  • concepts/unsigned-right-shift (new) — Java's >>>, C/C++'s (unsigned)x >> n; the language primitive that makes the (low + high) >>> 1 midpoint fix work in constant time irrespective of whether the sum overflowed.
  • patterns/safe-midpoint-computation (new) — the divide-and-conquer arithmetic shape: low + ((high - low) / 2) or (low + high) >>> 1 instead of (low + high) / 2. One pattern, covers binary search, mergesort, quicksort partitioning, every while (low <= high) loop body.
  • patterns/invariant-driven-programming (new) — the programming discipline of naming, writing down, and checking the invariants a piece of code relies on against the substrate semantics, not the intended / pseudocode semantics.

Caveats

  • One-blog-post-depth capture. The post is Bloch's short retrospective, not a paper. No benchmark data (e.g. how many JDK classes shipped with the bug, how many Google services were affected, exact dates/versions of the JDK fix), no repro script, no follow-on analysis of sibling divide-and-conquer algorithms that might still be wrong. The 2008 update from Antoine Trux is the only post-publication correction.
  • Primarily Java-centric. The concrete code is Java; the C/C++ fix is noted but not expanded; Rust, Go, Swift, etc. would each have their own idiom (e.g. Rust's usize::checked_add / saturating_add / wrapping_add make the invariant part of the type system). Wiki captures the universal shape but does not multiply across languages.
  • No pointer to the actual JDK fix commit — the post says "it was reported to Sun recently" but doesn't cite the bug-ID or fix. The JDK fix is Arrays.binarySearch at some point between ~2006–2007 (JDK 6-era); the wiki page notes the provenance without fabricating specifics.
  • The "ever vigilant" meta-lesson is intentionally soft. Bloch does not propose a new method; the post is a call for humility, not a new technique. The wiki treats the concrete arithmetic bug as the load-bearing claim and the epistemic framing as motivation for the adjacent verification-discipline pages (concepts/lightweight-formal-verification, patterns/property-based-testing, concepts/memory-safety).
  • Republication note. The Google Research blog surfaces this as a 2025-01-11 post but the prose is Bloch's 2006 original (plus the 2008 Trux correction). Treated here as a Google Research Tier-1 source because that is its current canonical home; the 2006 substance is unchanged.

Source

Last updated · 200 distilled / 1,178 read