Binäre Suche: vier Entscheidungen, sechzehn Schleifen

Triff die vier Entscheidungen im Code: die Schleifenbedingung, den Startwert von hi und die beiden Aktualisierungen. Daneben siehst du den Ablauf an einem kleinen sortierten Array, Durchlauf für Durchlauf. Die Prüfung erfasst jedes Array bis zur eingestellten Länge und jedes Ziel; den ersten Fehlerfall kannst du mit einem Klick aufrufen.

Rechenbeispiel — Binäre Suche: vier Entscheidungen, sechzehn Schleifen

Geprüfte Fälle	169
Mittelpunkt als (lo + hi) >> 1 mit 32 Bit	−1.064.671.149
Mittelpunkt als lo + ((hi − lo) >> 1)	1.082.812.499

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Binäre Suche: vier Entscheidungen, sechzehn Schleifen

Die binäre Suche findet einen Wert x in einem sortierten Array, indem sie einen Indexbereich von lo bis hi verwaltet, in dem x liegen muss, sofern es überhaupt vorkommt. Jeder Durchlauf liest das mittlere Element a[mid] und behält die Hälfte auf der Seite von x. Der Bereich ist abgeschlossen, wenn hi der letzte noch enthaltene Index ist (lo <= hi, hi beginnt bei n − 1), und halboffen, wenn hi der erste Index dahinter ist (lo < hi, hi beginnt bei n).

Was die einzelnen Symbole bedeuten

lo, hi: die Grenzen des noch zu durchsuchenden Bereichs
mid: ⌊(lo + hi)/2⌋, der in diesem Durchlauf gelesene Index
n: die Anzahl der Elemente an den Indizes 0 bis n − 1
N: die Länge des größten geprüften Arrays: jedes n von 0 bis N und jeder Zielwert, insgesamt (N + 1)² Fälle

Setzt voraus: Verschiedene Werte im Array, eine Schleife, die sofort zurückkehrt, sobald a[mid] gleich x ist, sowie bei Ablauf und Prüfung ganze Zahlen ohne Obergrenze. Für die Überlauftabelle entfällt die letzte Annahme; dort wird wie in Java mit 32 Bit gerechnet.
Versagt, wenn: Auch bei mehrfach vorkommenden Werten geben die beiden richtigen Schleifen einen Index zurück, an dem x steht, aber nicht unbedingt den ersten. Für den ersten Treffer, wie ihn eine Bereichsabfrage auf einem sortierten Index benötigt, darf die Schleife bei Gleichheit nicht anhalten: Der Bereich ist halboffen, bei a[mid] ≥ x gilt stets hi = mid, und nach dem Ende der Schleife ist lo die Antwort.

Vierzehn der sechzehn Schleifen sind falsch; zwei Elemente genügen als Nachweis 🖖

Bei jeder der vier Entscheidungen im Code muss sorgfältig gewählt werden, obwohl beide Möglichkeiten zunächst vernünftig wirken. Die Tabelle unter den Ergebnissen führt alle sechzehn Schleifen für jedes Array mit bis zu 12 Elementen und jeden Zielwert aus, insgesamt 169 Fälle. Zwei Schleifen bestehen. Jede andere scheitert an einem Array mit höchstens zwei Elementen, dreizehn der vierzehn sogar an einem Array mit einem Element oder am leeren Array. Stell die Prüfung auf 1 Element: Drei Schleifen bleiben übrig. Bei 2 sind es nur noch die beiden richtigen; selbst bei 256 verschiebt sich kein erster Fehlerfall. Diese kleinen Fälle bilden einen vollständigen Test und keine Stichprobe, denn die Schleife verwendet einen Wert ausschließlich für den Vergleich mit x. Jedes sortierte Array aus n verschiedenen Zahlen verhält sich wie 1, 3, 5 …, wobei der Zielwert einen seiner 2n + 1 möglichen Plätze einnimmt: auf einem Element oder in einer Lücke. Die Prüfung erfasst jeden dieser Plätze. Jon Bentley fasst die Schwierigkeit in Programming Pearls mit zwei Jahreszahlen zusammen: „Die erste binäre Suche wurde 1946 veröffentlicht, doch erst 1962 erschien eine binäre Suche, die für alle Werte von n korrekt funktioniert.“

Jede der beiden fast richtigen Schleifen verfehlt pro Array höchstens einen Suchwert 🖖

Drück auf Übersieht das letzte. Mit lo < hi und hi = n − 1 endet die Schleife, sobald lo und hi zusammentreffen, ohne das Element an dieser Stelle zu lesen. Jede Aktualisierung hält x im Bereich, und mid erreicht hi nie. Damit ist das einzige möglicherweise ungelesene Element jenes, bei dem hi beginnt: Die Schleife findet jedes Element jedes Arrays außer dem letzten. Drück auf Liest über das Ende, um das Spiegelbild zu sehen. Mit hi = n und lo <= hi liegt a[n] im Suchbereich, und nur ein Zielwert oberhalb aller Elemente lässt lo dorthin wandern. Bis 256 Elemente liegen die beiden Schleifen in 256 beziehungsweise 257 der 66.049 Fälle falsch. Allein beim Array mit 256 Elementen sind es 0,19 % der Zielwerte; hundert zufällige Zielwerte würden daher meist beide Fehler verfehlen. Das leere Array entlarvt die zweite Schleife in ihrem einzigen Fall, ein Array mit einem Element die erste. In JavaScript kommt die zweite Schleife sogar ungestraft davon: a[n] ist undefined, beide Vergleiche damit sind falsch, und die Schleife setzt hi = mid − 1 und liefert korrekt −1. In Java löst derselbe Zugriff eine Ausnahme aus, in C ist sein Verhalten undefiniert.

Die korrekte JDK-Schleife versagte jenseits von 2³⁰ Elementen 🖖

Die JDK-Schleife steht in der ersten Tabellenzeile. Sie ist in jedem prüfbaren Fall richtig und stammt von Joshua Bloch, der sie für java.util.Arrays schrieb. In Java ist lo + hi ein 32-Bit-int; jenseits von 2.147.483.647 läuft die Summe über und wird negativ. Ein am 11. Mai 2004 bei Sun eingereichter Fehlerbericht beschreibt die Suche nach dem letzten Element eines Arrays mit 1.100.000.000 Byte. Das Ergebnis war ArrayIndexOutOfBoundsException: -1064671149. Die Überlauftabelle wiederholt diese Suche, ohne Speicher für das Array zu reservieren: In Schritt 6 beträgt lo + hi genau 2.165.624.999. Nach Überlauf und Verschiebung ist der Mittelpunkt −1.064.671.149, dieselbe Zahl wie im Bericht. lo + ((hi − lo) >> 1) ergibt im selben Schritt 1.082.812.499. Laut Titel des Berichts versagt die Suche bei Arrays, die größer als 1<<30 sind, und diese Grenze stimmt genau: Gib 1.073.741.824 ein. Der größte Wert von lo + hi ist dann 2³¹ − 2 und passt noch in den Datentyp. Bei einem weiteren Element läuft die Suche in Schritt 31 über. Bloch schrieb 2006 über den Fehler, er habe „etwa neun Jahre lang“ unentdeckt gelauert. Auch Bentleys eigene, in Programming Pearls als korrekt bewiesene Fassung enthält ihn. Bentleys Satz, m werde auf den Mittelwert von l und u gesetzt und zur nächstkleineren ganzen Zahl abgerundet, gilt für ganze Zahlen, aber nicht für 32-Bit-Zahlen.

Aufgabe vollständig gelöst

Warum nur zwei Schleifen übrig bleiben 4 Schritte
Klick auf Hängt bei lo = mid. Die Prüfung kann Arrays mit höchstens 256 Elementen testen. Zeige für jedes n, dass die Schleife mit halboffenem Intervall und lo = mid + 1 immer endet, dass dieselbe Schleife mit lo = mid hängen bleibt, sobald hi = lo + 1 und a[lo] < x gilt, und welche Bedingung sich daraus für die Schleife mit geschlossenem Intervall ergibt.

Öffne diese Aufgabe im Tool
1. Bei der Schleife mit halboffenem Intervall wird der Rumpf nur ausgeführt, solange lo < hi gilt. Der abgerundete Wert von mid ist dann mindestens lo und echt kleiner als hi.
  
  $lo < hi \Rightarrow lo \leq ⌊ \frac{lo + hi}{2} ⌋ < hi$
2. Daher verringert hi = mid den Wert von hi um mindestens eins, und lo = mid + 1 erhöht lo um mindestens eins. In beiden Fällen sinkt hi − lo, anfangs gleich n, bei jedem Durchlauf um mindestens eins. Unter null kann die Differenz nicht fallen, also endet die Schleife nach höchstens n Durchläufen.
  
  $hi^{'} - lo^{'} \leq (hi - lo) - 1, n \to n - 1 \to \dots \to 0$
3. Betrachte nun lo = mid. Für hi = lo + 1 gilt mid = ⌊(2lo + 1)/2⌋ = lo. Ist außerdem a[lo] < x, bleibt lo durch die Aktualisierung unverändert, und der nächste Durchlauf wiederholt lediglich den vorigen. Das vorgegebene Beispiel erreicht diesen Zustand bei lo = 6, hi = 7, mit a[6] = 13 und x = 14.
  
  $hi = lo + 1 : ⌊ \frac{2 lo + 1}{2} ⌋ = lo \Rightarrow lo^{'} = lo, a [6] = 13 < 14$
4. Die Schleife mit geschlossenem Intervall läuft, solange lo <= hi gilt. Deshalb ist lo = hi zulässig; dann gilt mid = lo = hi. Eine Aktualisierung auf mid würde nichts verändern, also müssen beide Aktualisierungen über mid hinausgehen. Das ist möglich, weil a[mid] gerade gelesen wurde. Beim halboffenen Intervall ist hi bereits ausgeschlossen. Dort verwirft hi = mid das eben gelesene Element und alle Elemente darüber, die wegen a[mid] > x nicht infrage kommen. hi = mid − 1 würde zusätzlich a[mid − 1] verwerfen, obwohl dort x stehen könnte.
  
  $lo = hi \Rightarrow mid = lo = hi, [lo, hi) \to [lo, mid)$
Antwort

Jeder Durchlauf muss das Suchintervall verkleinern, darf nur Indizes ausschließen, an denen x nicht stehen kann, und das Anfangsintervall muss das gesamte Array umfassen. Für lo <= hi bedeutet das hi = n − 1, hi = mid − 1 und lo = mid + 1; für lo < hi gilt hi = n, hi = mid und lo = mid + 1. Die Prüfung bestätigt die beiden verbleibenden Varianten für Arrays mit bis zu 256 Elementen. Das Argument gilt für jedes n und leistet damit, was kein Test leisten kann. Bei 32-Bit-Arithmetik kommt eine weitere Voraussetzung hinzu: lo + hi muss darstellbar sein. Die dritte Erkenntnis zeigt, was geschieht, wenn diese Voraussetzung verletzt ist.

$\leq: (n - 1, mid - 1, mid + 1) <: (n, mid, mid + 1)$

Lernpfad

Warum ein Algorithmus korrekt ist

Quellen (2)

The overflow in the JDK's binary search, the nine years it went unnoticed, and Bentley's proved-correct version carrying the same line; also the source of the 1946 and 1962 dates the first insight quotes from Programming Pearls: Joshua Bloch, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken." Google Research Blog, 2 June 2006.
The bug report the page reproduces: java.util.Arrays.binarySearch on a 1,100,000,000-byte array, searching for its last element, throwing ArrayIndexOutOfBoundsException: -1064671149: OpenJDK bug JDK-5045582, "(coll) binarySearch() fails for size larger than 1<<30." Filed 11 May 2004 against Java 5.0, resolved (fixed in 6) 28 April 2006.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.

Binäre Suche: vier Entscheidungen, sechzehn Schleifen

Was die einzelnen Symbole bedeuten

Vierzehn der sechzehn Schleifen sind falsch; zwei Elemente genügen als Nachweis 🖖

Jede der beiden fast richtigen Schleifen verfehlt pro Array höchstens einen Suchwert 🖖

Die korrekte JDK-Schleife versagte jenseits von 230 Elementen 🖖

Die korrekte JDK-Schleife versagte jenseits von 2³⁰ Elementen 🖖