There is an error in almost all implementations of binary search and merge sort

This is a translation of Joshua Bloch's 2006 Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken .

I vividly remember the first lecture of John Bentley at Carnegie Mellon University, in which he asked us, freshly baked graduate students, to write a binary search function. He took one of the solutions and put it on the board, and, of course, there was a mistake in it, as in many of our other attempts. This case became for me a clear demonstration to his book “The Pearls of Programming”. The moral is to carefully arrange invariants in the program.

And now, now in 2006. I was shocked to learn that the binary search program, the correctness of which Bentley was formally proving with tests, contains an error. Do not think that I am carping; in truth, such an error may well elude testers for decades. Moreover, the binary search I wrote for the JDK was also nine years old. And just now, when she broke someone's program, they reported her in Sun.

So what is the mistake? Here is the standard binary search in Java, one of the ones I wrote for java.util.Arrays :
')

 public static int binarySearch(int[] a, int key) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; int midVal = a[mid]; if (midVal < key) low = mid + 1 else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } 

Error in the sixth line:

  int mid = (low + high) / 2; 

In “The Pearls of Programming”, Bentley writes at the expense of a similar line that she “sets m equal to the average of these numbers, rounded to the nearest smaller integer”. At first glance, everything is in order, but for sufficiently large low and high (namely, if their sum is more than 2 ³¹ -1) an error occurs. Their sum becomes a negative number, and mid also turns out negative. In C, this would result in unpredictable memory access outside the array, and Java throws an ArrayIndexOutOfBoundsException exception.

This error appears only on very large arrays, more than 2 ³⁰ (about a billion) elements. In the 80s, when the book saw the light, it would have been impossible, but now with us at Google (and indeed with any project) this is a common thing. In The Pearls of Programming, Bentley writes: “although the first version of the binary search was published in 1946, the correct code processing all n values ​​appeared only in 1962.” In fact, the correct code is still almost never met even in the most popular implementations of languages.

So how to write this code correctly? The sixth line can be rewritten as:

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

Although perhaps this option is faster and easier:

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

In C / C ++ there is no >>> operator, but you can write this:

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

Well, now we know for sure that there are no more errors, right? Well ... most likely. To absolutely strictly prove the correctness of the program, it needs to be tested on absolutely all possible input data, but in practice it is almost never feasible. And for parallel computing, it is still worse: you have to test the program for all possible internal states. Don't even try.

This error can come out in merge sorting in other algorithms of the “divide and conquer” type. If you implemented such algorithms, recheck them until the error has led to unpleasant consequences. Personally, this mistake taught me to be a little more modest and not to rely on the obviousness of even a small and familiar piece of code, not to mention the really complex systems that we use every day.

We, programmers, should improve our code by any means. Neat architecture design is good. Testing and formal analysis of algorithms is even better. Static analysis and code revision is just great. But none of this alone will save us from elusive bugs that will live for half a century, despite all our efforts. We must practice careful defensive programming and be vigilantly vigilant.

Update February 17, 2008. Antoine Trux , chief engineer at Nokia’s Finnish research center, reported that the proposed fix for C and C ++ does not guarantee correct operation, because by the standards of these languages, arithmetic overflow when added gives an uncertain result. Now that we have fixed this bug, we are sure that the program is working correctly. ;)

References:

• “ Programming Pearls ” - highly recommended, definitely buy it! (From the translator: the book was quoted in Russian translation )
  
• JDK Bug Tracker Error Message
  
• The 2003 Salvatore Ruggieri article on a more general, but perhaps less interesting, problem: finding the average of two entire arbitrary signs. The article does not address performance issues, and the proposed solution is not fast enough for an internal merge sort loop.