Binäre Suche — Algorithmus, Zeitkomplexität & Code

Die binäre Suche ist eine schnelle Methode, um ein Ziel in einer sortierten Liste zu finden. Du prüfst das mittlere Element, schließt die Hälfte der verbleibenden Werte aus und wiederholst den Vorgang. Ist die Liste nicht geordnet, funktioniert diese Logik nicht.

Bei einer aufsteigend sortierten Liste ist die Regel einfach: Ist der mittlere Wert kleiner als das Ziel, suche rechts; ist er größer, suche links. Weil sich der Bereich jedes Mal ungefähr halbiert, läuft die binäre Suche in $O(\log n)$ Zeit.

So funktioniert die binäre Suche in einer sortierten Liste

Verwende diese sortierte Liste:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Angenommen, das Ziel ist $31$.

Beginne mit dem gesamten Bereich. Der mittlere Wert ist $24$. Da $31 > 24$ gilt, kann alles links von $24$ ausgeschlossen werden, also geht die Suche weiter in

$$[31, 39, 45, 52]$$

Jetzt ist der mittlere Wert $39$. Da $31 < 39$ gilt, kann alles rechts von $39$ ausgeschlossen werden, also wird der Bereich zu

$$[31]$$

Nun ist der mittlere Wert $31$, also stoppt die Suche. Die wichtige Idee ist nicht nur, dass das Ziel gefunden wurde. In zwei Vergleichen ist der Kandidatenbereich von $9$ Werten auf $1$ gesunken.

Warum die binäre Suche $O(\log n)$ ist

Jeder Vergleich entfernt ungefähr die Hälfte der verbleibenden Kandidaten. Nach einem Schritt bleiben etwa $n/2$ Elemente übrig. Nach zwei Schritten bleiben etwa $n/4$ übrig. Nach $k$ Schritten ist die verbleibende Größe ungefähr

$$\frac{n}{2^k}$$

Die Suche endet, wenn diese Größe ungefähr $1$ ist, also gilt für die Anzahl der Schritte

$$2^k \approx n$$

Wenn man auf beiden Seiten den $\log_2$ nimmt, erhält man

$$k \approx \log_2 n$$

Deshalb skaliert die binäre Suche gut. Eine lineare Suche kann bis zu $n$ Prüfungen benötigen, aber die binäre Suche braucht nur so viele Prüfungen, wie nötig sind, um den Bereich immer weiter zu halbieren.

Codebeispiel für die binäre Suche

Hier ist eine übliche iterative Version in Python: