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)
- Durchschnitt Θ(log n)
- schlechtester Fall O(log n)
- Speicher O(1)
Was bedeutet das?
- 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.
- log₂ n: wie oft man n halbieren kann, bis 1 übrig ist. Bei 64 Werten sind das 6, also höchstens 7 Vergleiche.
- Mitte (mid)
- gefunden
- ausgeschlossen
- Ziel
Jede Mitte, die die Suche wählen könnte; ein Durchlauf ist ein Pfad nach unten. Ebenen: 5 = ⌈log₂(24 + 1)⌉, die meisten Vergleiche, die sie brauchen kann.
Suche 70 unter 24 sortierten Werten: Noch ist das ganze Array im Spiel.
Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.
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.