Binäre Suche
Findet einen Wert in einem sortierten Array, indem sie in die Mitte schaut und die Hälfte verwirft, in der er nicht sein kann. Jeder Vergleich halbiert, was übrig ist.
- bester Fall Ω(1)
- Θ(log n)
- schlechtester Fall O(log n)
- Speicher O(1)
log₂ n: wie oft man n halbieren kann, bis 1 übrig ist. Bei 64 Werten sind das 6, also höchstens 7 Vergleiche.
Weitere Begriffe auf dieser Seite
- Sortiert: aufsteigend geordnet. Die binäre Suche braucht das; auf unsortierten Daten liefert sie falsche Antworten.
- Halbieren: Jeder Vergleich verwirft die Hälfte des Rests, die Hälfte, in der das Ziel nicht sein kann.
- Mitte (mid)
- gefunden
- ausgeschlossen
- Ziel
Probieren Sie es aus: Wähle ein Ziel, das nicht im Array ist. Die Suche endet trotzdem nach höchstens ⌈log₂(n + 1)⌉ Vergleichen, wenn lo das hi überholt.
So funktioniert es
Die binäre Suche hält zwei Marken, lo und hi, um den Teil des Arrays, in dem das Ziel noch sein kann. Sie schaut auf den Wert in der Mitte: Ist er das Ziel, fertig; ist er kleiner, kann das Ziel nur rechts liegen, also rückt lo hinter die Mitte; ist er größer, rückt hi davor. Jeder Schritt halbiert den Rest, sodass 64 Werte höchstens 7 Vergleiche brauchen und eine Million höchstens 20. Überholt lo das hi, ist nichts mehr übrig: Der Wert ist nicht im Array.
Wann es sich eignet
Binäre Suche passt immer, wenn die Daten sortiert sind und man zu jeder Position springen kann: ein Wort in einer sortierten Liste, eine Version in der Release-Historie, git bisect, die Einfügestelle in einem sortierten Array. Auf unsortierten Daten liefert sie falsche Antworten, und vorher zu sortieren lohnt sich erst bei vielen Suchen.