Binäre Suche
So schlagen Sie ein Wort im Wörterbuch nach: in der Mitte aufschlagen, prüfen, ob das Wort davor oder danach kommt, und mit dieser Hälfte wiederholen. Genau das ist die binäre Suche. In einer sortierten Liste findet sie jeden Wert unter einer Million in höchstens 20 Vergleichen.
Die Idee
In einer sortierten Liste verrät ein Vergleich mehr als nur, ob Sie das Ziel gefunden haben: Er verrät, auf welcher Seite das Ziel liegt. Vergleichen Sie das Ziel mit dem Wert in der Mitte. Sind beide gleich, sind Sie fertig. Ist der mittlere Wert kleiner, ist auch alles davor kleiner, also kann das Ziel nur dahinter liegen. Ist er größer, kann das Ziel nur davor liegen. Behalten Sie nur diese Hälfte und wiederholen Sie.
Ein Beispiel
Suchen Sie in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 nach 23. Der mittlere Wert ist 16, also kleiner, daher bleiben nur 23 bis 91. Deren Mitte ist 56, also größer, daher bleiben nur 23 und 38. Deren Mitte ist 23: gefunden an Platz 6 nach 3 Vergleichen, wo die lineare Suche 6 braucht. Sucht man in derselben Liste nach 40, werden 16, 56, 23 und 38 verglichen, danach bleibt nichts übrig: 4 Vergleiche, um zu wissen, dass 40 fehlt, gegenüber 10 bei der linearen Suche.
Halbieren wirkt schnell
Nach einem Vergleich bleibt höchstens die Hälfte der Liste, nach zwei ein Viertel, nach k höchstens etwa n/2ᵏ. Die Suche endet, wenn nichts mehr übrig ist, also braucht sie höchstens ⌊log₂ n⌋ + 1 Vergleiche: 6 bei 40 Werten, 10 bei 1.000, 20 bei einer Million und 30 bei einer Milliarde. Eine doppelt so lange Liste kostet nur einen Vergleich mehr. Man schreibt das O(log n).
Leicht beschrieben, schwer richtig umgesetzt
John Mauchly beschrieb die binäre Suche 1946, doch laut Donald Knuth erschien die erste Version, die für jede Listenlänge funktionierte, erst 1962. Jon Bentley stellte später fest, dass nur etwa jeder zehnte Berufsprogrammierer sie richtig schrieb: Die Abbruchbedingungen und das Plus oder Minus eins beim Teilen der Hälften gehen leicht schief. 2006 zeigte Joshua Bloch, dass der übliche Weg, die Mitte zu finden, (low + high) / 2, bei sehr langen Listen überlaufen kann – ein Fehler, der jahrelang in der Java-Bibliothek steckte. Die Schreibweise low + (high − low) / 2, wie sie die App nutzt, vermeidet ihn.
Varianten und Anwendungen
Bei Duplikaten findet die binäre Suche einen der Treffer; Versionen, die nach links oder rechts weitersuchen, finden den ersten oder letzten oder die Stelle, an der ein fehlender Wert eingefügt würde. Dieselbe Halbierungsidee findet die Nullstelle einer Gleichung (Bisektion), die Version, in der ein Fehler zuerst auftrat (git bisect), und die Antwort auf viele Optimierungsrätsel. Binäre Suchbäume speichern Daten so, dass jede Suche demselben Halbierungsweg folgt.
Selbst ausprobieren
Öffnen Sie die App, wählen Sie unter „Suchen nach“ einen Wert und drücken Sie „Schritt“. Der schattierte Bereich zeigt, wo das Ziel noch sein kann; der mittlere Wert ist hervorgehoben, und die ausgeschlossene Hälfte verblasst. Die Kacheln zeigen, wie viele Werte noch möglich sind und wie viele Vergleiche eine lineare Suche für denselben Wert bräuchte. Suchen Sie nach einem fehlenden Wert oder nehmen Sie 40 Balken, um den Abstand wachsen zu sehen.
Häufig gestellte Fragen
Welche Zeitkomplexität hat die binäre Suche?
O(log n): höchstens ⌊log₂ n⌋ + 1 Vergleiche bei n Werten. Im besten Fall reicht ein Vergleich, wenn das Ziel in der Mitte liegt. Die iterative Version braucht O(1) zusätzlichen Speicher.
Was ist der Unterschied zwischen binärer und linearer Suche?
Die lineare Suche prüft jeden Wert der Reihe nach und funktioniert mit jeder Liste, kann aber n Vergleiche brauchen. Die binäre Suche funktioniert nur mit einer sortierten Liste, schließt aber mit jedem Vergleich die Hälfte des Rests aus und braucht daher etwa log₂ n.
Lohnt es sich, eine Liste nur für die binäre Suche zu sortieren?
Nur wenn Sie oft darin suchen. Sortieren braucht etwa n log n Schritte, mehr als eine einzelne lineare Suche. Ist die Liste einmal sortiert, ist jede weitere Suche sehr günstig.
Funktioniert die binäre Suche auch mit anderem als Listen?
Ja, mit allem, bei dem ein Test verrät, auf welcher Seite der Antwort Sie sind: ein Zahlenbereich, die Versionen eines Programms oder die Tipps bei einem Höher-oder-tiefer-Spiel.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Binäre Suche ausprobieren