Binäre Suche einfach zu implementieren?

Binary Search einfach zu implementieren?
Die meisten Informatikstudenten würden dies ohne mit der Wimper zu zucken mit "Ja" beantworten.

Aber wie Joshua Bloch, einer der Chef-Entwickler von Java und nun bei Google, im Research Blog von Google darstellt, sind nahezu alle Implementierungen der binären Suche inkl. der Implementierung in der Java-Klassenbibiothek fehlerhaft.

Der Code im JDK so laut dem Blogeintrag so aus:

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low < = high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1;
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

Das Problem liegt in Zeile 6. Wenn die Summe von low und high größer ist als 2 hoch 31 - 1 wird in Java ein ArrayIndexOutOfBoundsException geworfen. In C und C++ ist das verhalten noch unberechenbarer: Es findet ein Überfluss in eine negative Zahl statt und es wird auf Speicherbereiche vor dem Array zugegriffen.

Boach schlät folgende Verbesserungen vor:

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

Alternative wäre auch folgendes gut, da es klarer und schneller sei:

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

Diese Fehler scheint über Jahrzehnte unbemerkt geblieben zu sein. Der Code (low + high) / 2 findet sich in nahezu jedem Lehrbuch. Bloch spricht dabei das Buch "Programming Pearls" an, dass er den Leser trotzdem empfiehlt. Ich habe in jedem Algorithmenbuch, dass ich besitze nachgesehen und überall ist der gleiche Bug zu finden. Corman macht es sich einfach und hat die binäre Suche nur als Übungsaufgabe für die Leser erwähnt.

So lange ein solcher Code nur in Pseudocode angegeben wird und vorher die Annahme vereinbart wurde, dass es keinen begrenzten Wertebereich gibt, mag dies formal in Ordnung sein.
Doch sobald man diesen Pseudocode übersetzt, kommt es zu dem Bug in der Implementierung.

Bloch schließt mit:

It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.

We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

P.S. Implementierungen von Mergesort sowie anderen Divide-and-Conquer-Algorithemen scheinen ebenfalls betroffen zu sein.