Binäre Suche: Ablauf, Beispiel und Laufzeit

Stell dir vor, du vergleichst den Suchwert mit dem mittleren Element. Nur bei einer sortierten Folge kannst du daraus sicher ableiten, welche Hälfte nicht mehr infrage kommt.

Ist der Suchwert kleiner als der mittlere Wert, kann er nur links davon liegen. Ist er größer, kann er nur rechts davon liegen. Genau dieses Ausschließen einer ganzen Hälfte macht die binäre Suche schnell.

Binäre Suche und Sortierung müssen dieselbe Ordnung verwenden. In einem nach Namen sortierten Telefonbuch kannst du binär nach einem Namen suchen, aber nicht unmittelbar nach einer Telefonnummer.

Für ein Array mit den Indizes 0 bis n - 1 setzt du zunächst links = 0 und rechts = n - 1.

Dann wiederholst du diese Schritte, solange links <= rechts gilt:

1. Berechne die Mitte mit mitte = links + (rechts - links) // 2. // bedeutet ganzzahlige Division mit Abrunden.
2. Vergleiche den Wert an der Position mitte mit dem Suchwert.
3. Bei Gleichheit ist die Suche erfolgreich.
4. Ist der mittlere Wert größer, setze rechts = mitte - 1.
5. Ist der mittlere Wert kleiner, setze links = mitte + 1.

Die Mitte selbst wurde bereits geprüft. Deshalb wird sie durch mitte - 1 oder mitte + 1 aus dem neuen Bereich entfernt. Ohne dieses Vorbeibewegen könnten Grenzen stehen bleiben und die Schleife endlos laufen.

Die verwendete Mittenformel ist außerdem robuster als (links + rechts) / 2, weil die Addition der beiden möglicherweise großen Indizes vermieden wird.

Ein Wert fehlt, wenn der Suchbereich leer wird. Das erkennst du an links > rechts: Der linke Rand liegt dann rechts vom rechten Rand, also bleibt keine ungeprüfte Position übrig.

Programme können einen Misserfolg unterschiedlich melden, etwa mit -1, None oder einer Einfügeposition. Diese Rückgabekonvention gehört zur jeweiligen Implementierung; das Abbruchkriterium bleibt der leere Suchbereich.

Eine lineare Suche prüft die Elemente der Reihe nach und benötigt im ungünstigsten Fall bis zu n Vergleiche. Die binäre Suche verwirft nach jedem Vergleich ungefähr die Hälfte der noch möglichen Positionen.

Bei 12 Elementen genügen im schlechtesten Fall 4 Vergleiche. Das passt zur Formel

$$\left\lceil\log_2(n+1)\right\rceil$$

Denn für n = 12 gilt: 2³ = 8 < 13 <= 16 = 2⁴. Daher ist die aufgerundete Zweierlogarithmus-Zahl 4.

Allgemein wächst die Laufzeit im schlechtesten Fall wie

$$\mathcal O(\log n)$$

Der beste Fall benötigt nur einen Vergleich: Das zuerst geprüfte mittlere Element ist bereits der Suchwert.

Vertiefung: Iteration und Rekursion

Eine iterative Umsetzung aktualisiert links und rechts in einer Schleife und benötigt konstanten zusätzlichen Speicher, also $\mathcal O(1)$.

Eine rekursive Umsetzung halbiert denselben Bereich durch Funktionsaufrufe. Dafür werden Aufrufzustände gespeichert; der zusätzliche Speicherbedarf wächst bis zu $\mathcal O(\log n)$.

Der Geschwindigkeitsvorteil gilt nur, wenn die Daten bereits passend sortiert sind und direkt auf das mittlere Element zugegriffen werden kann. Bei einer einfachen verketteten Liste kostet schon das Erreichen der Mitte zusätzlichen Aufwand. Muss eine unsortierte Folge erst sortiert werden, gehört auch dieser Aufwand zur Gesamtbetrachtung.

Du beherrschst die binäre Suche, wenn du vor dem Start die Sortierung prüfst, nach jedem Vergleich die richtige Grenze an der Mitte vorbeibewegst und bei links > rechts sicher auf Misserfolg schließt.