Stell dir vor, du schlägst ein Wort in einem dicken Wörterbuch nach. Schlägst du auf der ersten Seite auf und arbeitest dich Seite für Seite vor? Natürlich nicht! Du öffnest das Buch in der Mitte, siehst ob das Wort vor oder nach dieser Stelle kommt, und teilst dann die verbleibende Hälfte wieder in der Mitte auf. Das ist genau die Idee hinter der binären Suche.
Voraussetzung: Sortierte Liste
Die binäre Suche funktioniert nur auf sortierten Listen. Das ist der entscheidende Unterschied zur linearen Suche.
Grundprinzip
- Betrachte das mittlere Element der Liste.
- Ist es der gesuchte Wert? Fertig!
- Ist der gesuchte Wert kleiner? Suche nur noch in der linken Hälfte.
- Ist der gesuchte Wert größer? Suche nur noch in der rechten Hälfte.
- Wiederhole, bis der Wert gefunden wird oder der Suchbereich leer ist.
Visualisierung
Suche nach 23 in [2, 5, 8, 12, 16, 23, 38, 42]:
| Schritt | Links | Rechts | Mitte | Wert | Aktion |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 12 | 23 > 12 → rechte Hälfte |
| 2 | 4 | 7 | 5 | 23 | Gefunden! |
Nur 2 Vergleiche statt potenziell 8!
Python-Implementierung
def binaere_suche(liste, zielwert):
links = 0
rechts = len(liste) - 1
while links <= rechts:
mitte = (links + rechts) // 2 # mittlerer Index
if liste[mitte] == zielwert:
return mitte # gefunden!
elif liste[mitte] < zielwert:
links = mitte + 1 # rechte Hälfte weitersuchen
else:
rechts = mitte - 1 # linke Hälfte weitersuchen
return -1 # nicht gefunden
zahlen = [2, 5, 8, 12, 16, 23, 38, 42]
print(binaere_suche(zahlen, 23)) # 5 (Index)
print(binaere_suche(zahlen, 10)) # -1 (nicht gefunden)
(links + rechts) // 2 berechnet den mittleren Index mit ganzzahliger Division. Wenn die Liste eine gerade Anzahl von Elementen hat, wird der untere der beiden mittleren Indizes gewählt.
Warum ist die binäre Suche so viel schneller?
Bei jedem Schritt wird der Suchbereich halbiert:
| Schritte | Maximal durchsuchbare Elemente |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 7 | 128 |
| 10 | 1.024 |
| 20 | 1.048.576 |
Mit nur 20 Schritten kann die binäre Suche über eine Million Elemente durchsuchen! Das nennt sich O(log n) — logarithmische Zeitkomplexität.
Der Vergleich in Zahlen: Um 1.000.000 Elemente zu durchsuchen, braucht die lineare Suche im Durchschnitt 500.000 Vergleiche. Die binäre Suche braucht maximal 20 Vergleiche. Das ist ein riesiger Unterschied!
Lineare vs. Binäre Suche
| Eigenschaft | Lineare Suche | Binäre Suche |
|---|---|---|
| Voraussetzung | Keine | Liste muss sortiert sein |
| Zeitkomplexität | O(n) | O(log n) |
| 1.000 Elemente | bis 1.000 Vergleiche | bis 10 Vergleiche |
| Einfachheit | Sehr einfach | Mittel |
Die binäre Suche funktioniert nur korrekt, wenn die Liste vollständig sortiert ist. Auf einer unsortierten Liste liefert sie falsche Ergebnisse — sie schließt eventuell Bereiche aus, die das gesuchte Element enthalten.
Übungsaufgaben
Wie viele Schritte benötigt die binäre Suche maximal, um ein Element in einer sortierten Liste mit 16 Elementen zu finden?
Antwort anzeigen
Warum kann man die binäre Suche nicht auf eine unsortierte Liste anwenden?