Joshua Bloch’s Java Binary Search Failed Past a Billion Elements. A Version Proven Correct Had the Same Bug.

In June 2006, Joshua Bloch admitted on Google’s research blog that the binary search he had written for Java’s standard library contained a bug. He reported something more unsettling too. The binary search that Jon Bentley had proved correct in his book Programming Pearls had the same bug.

In both versions, the bug sat in the line that finds the middle of the range still being searched, between a low and a high index. In Bloch’s post it read:

int mid = (low + high) / 2;

On paper, nothing is wrong with it. In Java, though, low and high are 32-bit integers, and an int cannot hold a value above 2,147,483,647. In an array of more than 1,073,741,824 elements — 2 to the 30th power — low + high can pass that limit. The sum wraps around to a negative number, and the search asks for an element at a negative index.

Bloch wrote that the bug had been reported to Sun Microsystems, then Java’s developer, “when it broke someone’s program, after lying in wait for nine years or so.” His headline drew the wider conclusion: nearly all binary searches and mergesorts are broken.

A lesson Bloch had first learned from Bentley

Bentley was well aware of how easily binary search goes wrong. Bloch’s post quotes him on the history: while the first binary search was published in 1946, “the first binary search that works correctly for all values of n did not appear until 1962.” Donald Knuth’s history of the algorithm credits D. H. Lehmer with one in 1960. Bentley’s own version in Programming Pearls came with a proof, and he tested it as well.

Bloch had learned the same lesson from Bentley in person. In Bentley’s first algorithms lecture at Carnegie Mellon University, he asked the incoming PhD students, Bloch among them, to write a binary search, then took one of their attempts apart in front of the class. It was broken, Bloch recalled, “as were most of our implementations.”

How a byte array exposed the bug

In a sorted array, binary search compares the value it wants with the middle element and discards the half that cannot contain it, so even a billion elements take only about 30 halvings.

A report in Sun’s bug database, filed on May 11, 2004, shows how little it took to trigger the bug. The test created a byte array of 1,100,000,000 elements, set the last one to 1 and searched for it. Each step pushed low higher, until low + high passed the int limit. The Java 5 beta then threw an ArrayIndexOutOfBoundsException for index −1,064,671,149.

No exotic hardware was involved. The machine ran 32-bit Linux, Java was given a maximum heap of 1,200 megabytes, and a byte array of 1.1 billion elements needs about 1.1 gigabytes.

The library’s code at the time differed slightly from the line in Bloch’s post: it used a bit shift instead of division, (low + high) >> 1, and overflowed the same way. The reporter proposed the fix, an unsigned shift written >>>, and noted that the TreeMap class computed its midpoints with the same faulty sum.

The bug report came before the blog post

The 2004 report stayed unresolved for almost two years. On April 12, 2006, Martin Buchholz, the engineer assigned to it, filed the problem again; that newer report, closed as a duplicate, is the one Bloch’s post linked. On April 28, Sun marked the bug fixed for Java 6, in build 83, about five weeks before Bloch’s post.

So Bloch did not discover the bug. What his post did was explain it, admit his own part in it and show how far it reached: “The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms.”

Why Bentley’s proof did not catch the overflow

Bentley, whose version calls the indexes l and u, described the line’s job in words: it “sets m to the average of l and u, truncated down to the nearest integer.” For the integers of mathematics, the line does exactly that. For 32-bit ints, it does so only while l + u fits.

When Programming Pearls was written, arrays big enough to make that sum overflow were, in Bloch’s words, “inconceivable back in the ’80s.” By 2006, he wrote, they were common at Google and other places. The proof had not changed. The arrays had grown past it.

Two fixes, and a fix that needed fixing

Bloch offered two repairs for Java. One avoids the large sum altogether:

int mid = low + ((high - low) / 2);

The other keeps the sum but reads it differently:

int mid = (low + high) >>> 1;

Java’s >>> operator shifts in a zero from the left, so it treats the 32 bits of an overflowed sum as an unsigned number. Two valid indexes always add up to less than 2 to the 32nd power, so the result is the correct midpoint. Today’s OpenJDK source, the open-source code base of Java, uses this form.

The C and C++ fix needed its own fix. Bloch’s first suggestion for those languages was not guaranteed to work under C99, the 1999 version of the C standard, because that standard leaves the result of a signed integer overflow undefined. In a 2008 update, crediting Antoine Trux of Nokia Research Center for the catch, Bloch replaced it with a version that adds the two indexes as unsigned integers.

What the bug shows about proofs and scale

A proof covers its model, not the machine. Bentley’s reasoning held for integers that never run out. Java’s int runs out at 2,147,483,647. On paper, “the average of l and u” always exists. In a 32-bit int, l + u may not fit.

Scale turns safe assumptions into bugs. The midpoint line was harmless for every array of up to about a billion elements. Index arithmetic that is safe at today’s sizes can overflow at tomorrow’s.

A test covers only the inputs it runs. Bentley had tested his program too, and the bug survived both the proof and the tests. Bloch’s own conclusion was blunt: “It is not sufficient merely to prove a program correct; you have to test it too.” The 2004 report needed a few lines of code and a little over a gigabyte of memory to make the failure visible.

The final repair in Java was tiny. The line that failed in 2004 read (low + high) >> 1. The line in today’s OpenJDK, in a class that still lists Bloch among its authors, reads (low + high) >>> 1: one extra character, marking the difference between the integers of a proof and the integers of a machine.

Explore

Stay connected