Bei Algorithmen, die nach dem Teile-und-Beherrsche-Prinzip vorgehen oder bei Halbierungsverfahren, muss meist die Mitte eines Bereichs (eines Felds) berechnet werden. Der Bereich ist oft durch seine linke untere und rechte obere Grenze definiert. Dies sieht dann meist so aus:
int mitte = (links + rechts) / 2;
Diese Berechnung funktioniert in Java und anderen Programmiersprachen nicht immer. Was passiert, wenn die rechte Grenze sehr gross wird und der Bereich sich sehr weit rechts befindet? Wie muß die Mitte in Java berechnet werden, damit in jedem Fall das Ergebnis der Berechnung stimmt?
Dieser Fehler findet sich häufig in Lehrbüchern aber auch in Programmbibliotheken. In der Java-Version 1.6 wird in der Klasse Arrays die Mitte für die Binärsuche wie folgt berechnet (dabei ist aus Geschwindigkeitsgründen die Division durch 2 durch einen Rechts-Shift ersetzt):
int mid = (low + high) >>> 1;
