Binäre Suche

Die rekursive binäre Suche aus Sedgewick/Wayne, Listing 1.1 – zum Zuschauen, mit Aufrufstapel und Java-Code.

So geht’s: Wähle eine Zahl, die im Array steht, oder eine, die fehlt, und spiele die Suche ab – oder geh mit „Schritt“ einzeln durch. Blau ist der aktuelle Suchbereich lo..hi, orange das geprüfte Element a[mid]. Rechts wächst und schrumpft der Aufrufstapel: Jede Halbierung ist ein neuer Aufruf von rank, und das Ergebnis wird Ebene für Ebene zurückgereicht.

Erklärung

Das ist Listing 1.1 aus Sedgewicks Algorithmen: die rekursive binäre Suche. Sie findet den Index von key in einem sortierten Array a[] oder gibt -1 zurück, wenn key nicht vorkommt.

Die zwei Methoden

rank(key, a) ist nur eine Hülle. Sie startet die Suche über das ganze Array, also von lo = 0 bis hi = a.length - 1.
rank(key, a, lo, hi) erledigt die eigentliche Arbeit und sucht nur im Bereich a[lo..hi].

So läuft ein Aufruf ab

Abbruch: Ist lo > hi, ist der Suchbereich leer, und die Methode gibt -1 zurück („nicht gefunden“).
Mitte bestimmen: mid = lo + (hi - lo) / 2. Diese Schreibweise statt (lo + hi) / 2 verhindert einen Integer-Überlauf bei sehr großen Indizes.
Vergleichen:
- Ist key < a[mid], wird links weitergesucht (lo bis mid - 1).
- Ist key > a[mid], wird rechts weitergesucht (mid + 1 bis hi).
- Sonst gilt key == a[mid], und die Methode gibt mid zurück.

Der Kommentar im Code beschreibt die Invariante: Wenn key im Array vorkommt, dann liegt er immer im Bereich zwischen lo und hi. Jeder rekursive Aufruf hält diese Bedingung ein und halbiert dabei den Bereich.

Beispiel: a = {10, 20, 30, 40, 50, 60, 70}, gesucht ist key = 60.

Erster Aufruf: lo=0, hi=6, mid=3. Es ist a[3]=40 < 60, also geht es rechts weiter.
Zweiter Aufruf: lo=4, hi=6, mid=5. Es ist a[5]=60, also Treffer. Rückgabe: 5.

Laufzeit: Weil sich der Bereich bei jedem Schritt halbiert, braucht die Suche höchstens etwa log₂(n) + 1 Vergleiche. Bei einer Million Elementen sind das rund 20. Das ist der Grund, warum der Text auf Kapitel 3.2 verweist: Dort wird diese Laufzeit mathematisch genau untersucht.

Der Text über dem Code bezieht sich auf die Regeln für Rekursion: Es muss einen Basisfall geben, und jeder rekursive Aufruf muss ein kleineres Teilproblem bearbeiten. Hier ist der Basisfall lo > hi, und die Teilprobleme überlappen sich nicht. Die Bereiche lo..mid-1 und mid+1..hi sind also disjunkt.