Innerhalb der Aktion "Algorithmus der Woche" wird beginnend am 7. März die "binäre Suche" vorgestellt. Auf dieser Seite finden Sie weiterführende Informationen und Links auf zusätzliches Material zu diesem Thema.
Rekursive Implementierung
Im "Algorithmus der Woche" wird eine "iterative" Implementierung der binären Suche präsentiert, d. h. das Ergebnis wird durch wiederholten Schleifendurchlauf berechnet. Alternativ kann man die binäre Suche auch mit einer "rekursiven" Funktion implementieren; das ist eine Funktion, die sich im Funktionsrumpf selbst aufruft:
BinaereSuche(A, Schluessel, links, rechts) 1 if links > rechts return "nicht gefunden" 2 mitte := (links + rechts) / 2 {Mitte bestimmen, Ergebnis runden} 3 if A[mitte] = Schluessel then return mitte 4 if A[mitte] > Schluessel then return BinaereSuche(A, Schluessel, links, mitte-1) 5 if A[mitte] < Schluessel then return BinaereSuche(A, Schluessel, mitte+1, rechts)
Dabei ist "A" wieder das zu durchsuchende Array, "Schluessel" der gesuchte Schlüssel und "links" und "rechts" die linke und rechte Grenze des zu durchsuchenden Bereichs in A. Soll der Eintrag "Nelly" in dem Array "Regal" mit 500 Einträgen gesucht werden, wir also zunächst wieder BinaereSuche(Regal, "Nelly", 1, 500) aufgerufen. Anders als bei der iterativen Lösung werden dann jedoch die Grenzen nicht innerhalb einer Schleife aufeinander zugeschoben, sondern einfach die BinaereSuche-Funktion mit entsprechend angepassten Grenzen "rekursiv" aufgerufen. Man erhält z. B. die folgende Sequenz von Aufrufen:
BinaereSuche(Regal, "Nelly", 1, 500)
BinaereSuche(Regal, "Nelly", 251, 500)
BinaereSuche(Regal, "Nelly", 251, 374)
BinaereSuche(Regal, "Nelly", 313, 374)
BinaereSuche(Regal, "Nelly", 344, 374)
...
Binäre Suche ohne obere Grenze
In der Praxis kann es vorkommen, dass die obere Grenze (d.h. die Länge) des zu durchsuchenden (sortierten) Arrays nicht bekannt ist. Auch in diesem Fall kann die binäre Suche angewandt werden. Zuerst wird die rechte Grenze auf 1 gesetzt und dann so lange verdoppelt, bis der an der rechten Grenze gespeicherte Schlüsselwert größer als der Suchschlüssel ist:
rechts := 1
while A[rechts] < Schluessel do rechts := 2 * rechts
Anschließend kann dann die binäre Suche aufgerufen werden, wobei als linke Grenze rechts/2 gewählt wird. Für das gesamte Verfahren werden dabei nicht mehr als 2 * log2 k Schritte benötigt, wobei k die Arrayposition desjenigen Eintrags ist, der den Suchschlüssel enthält.
Alternative Halbierung des Suchraums
Beim "Algorithmus der Woche" wird vorgestellt, wie man mit mithilfe der binären Suche möglichst schnell eine gedachte Zahl erraten kann. Um dabei nicht immer dieselbe langweilige Frage "Ist die Zahl größer/kleiner als ...?" stellen zu müssen, kann man auch mal ein "Ist die Zahl (un)gerade?" einstreuen. Dadurch fällt auch die Hälfte der verbleibenden Möglichkeiten weg. Ebenso kann gefragt werden "Ist die Zehner-/Hunderter-/Tausender-/...-Stelle (un)gerade?". Auch damit erreicht man jeweils (ungefähr) eine Halbierung des Suchraums. Sind alle Stellen durchgetestet, muss man jedoch wieder auf die übliche Halbierung zurückgreifen (wobei dann die bereits ausgeschlossenen Zahlen zu berücksichtigen sind).
Ganz einfach wird die Sache, wenn man sich die Zahl als Binärzahl vorstellt. Während im Dezimalsystem Zahlen als Vielfache von Zehnerpotenzen dargestellt werden, z. B.
107 = 1 * 102 + 0 * 101 + 7 * 100
107 = 1 * 100 + 0 * 10 + 7 * 1,
werden Zahlen im Binärsystem als Vielfache von Zweierpotenzen dargestellt:
Die Binärdarstellung von 107 ist also 1101011. Um eine Zahl mithilfe der Binärdarstellung zu erraten, reicht es zu wissen, wie viele Binärstellen die zu erratende Zahl maximal haben kann. Die Anzahl der Binärstellen kann man wieder einfach mit dem Zweierlogarithmus berechnen. Soll z. B. eine Zahl zwischen 1 und 1000 erraten werden, berechnet man
log2 1000 » 9,97 (aufrunden!),
es werden also 10 Stellen benötigt. Danach reichen 10 Fragen: "Ist die erste Binärstelle gleich 1?", "Ist die zweite Binärstelle gleich 1?", "Ist die dritte Binärstelle gleich 1?", usw. Danach sind alle Stellen der Binärdarstellung der Zahl bekannt, und man muss nur noch ins Dezimalsystem umrechnen; das kann dann wieder der Taschenrechner übernehmen.
