12.2 Binäre Suche

Die binäre Suche

Wenn die zu durchsuchenden Daten sortiert sind, kann man ein sehr viel effizienteres Suchverfahren anwenden als die lineare bzw. sequentielle Suche, nämlich die binäre Suche.

Die binäre Suche erfolgt nach dem Prinzip "Teile und herrsche". Das heißt, man teilt die zu durchsuchenden Daten in zwei Hälften und ermittelt dann, in welcher Hälfte das zu suchende Element vorkommt. Die andere Hälfte kann ignoriert werden. So wird bereits in dem ersten Suchschritt die Menge der zu durchsuchenden Daten um 50% reduziert.

Stellen Sie sich vor, Sie stehen vor einem Bücherregal, und die Bücher sind nach Autoren aufsteigend alphabetisch sortiert. Sie suchen nun nach einem Buch des Autoren Max Frisch, weil Sie das gerade im Deutsch-Kurs behandeln. Sie beginnen Ihre Suche in der Mitte des Regals, wo mit hoher Wahrscheinlichkeitkeit Autoren wie Klaus Mann oder Karl May stehen. Sofort erkennen Sie: Max Frisch muss in der linken Hälfte untergebracht sein. Die rechte Hälfte des Regals können Sie ignorieren, Sie haben also die zu durchsuchende Datenmenge um 50% reduziert.

Nun stellen Sie sich ungefähr in der Mitte der linken Hälfte auf und schauen, welche Autoren dort vorkommen. Die Autoren fangen alle mit 'E' an. Max Frisch muss sich also in der rechten Hälfte der linken Hälfte befinden. Sie gehen zur Mitte dieses Viertels und machen genau so weiter, bis Sie schließlich ihren Max Frisch gefunden haben, oder bis sie festgestellt haben, dass sie das Buch wohl verliehen oder wo anders hingelegt haben.

Eine halb-quantitative Einschätzung der Suchzeit

Wir suchen die Zahl 16 in einem sortierten Array:

Zunächst teilen wir den Array in zwei Hälften mit je 16 Elementen

Die größte Zahl der linken Hälfte ist größer als die Suchzahl 16, also machen wir in der linken Hälfte weiter und ignorieren die rechte Hälfte.

Die linke Hälfte wird jetzt wieder in zwei Hälften unterteilt:

Die größte Zahl in der linken Hälfte ist kleiner als die Suchzahl 16, daher machen wir in der gelb markierten rechten Hälfte des Teilarrays weiter. Diese unterteilen wir wieder in zwei Hälften:

Die größte Zahl der linken Hälfte ist größer als die Suchzahl 16, also machen wir in der linken Hälfte weiter und ignorieren die rechte Hälfte.

Die größte Zahl der linken Hälfte stimmt mit der Suchzahl überein, also können wir das Suchen mit Erfolg beenden.

Einschätzung der Suchzeit

• Der Array hat 32 Elemente (Index 0..31).
• Der Index der größten Zahl der linken Hälfte ist dann 15 (Rechenoperation 1).
• Wir vergleichen diese Zahl (32) mit der Suchzahl (16) (Rechenoperation 2).
• Der Index der größten Zahl der linken Hälfte ist dann 7 (Rechenoperation 3).
• Wir vergleichen diese Zahl (14) mit der Suchzahl (16) (Rechenoperation 4).
• Der Index der größten Zahl der linken Hälfte ist dann 11 (Rechenoperation 5).
• Wir vergleichen diese Zahl (21) mit der Suchzahl (16) (Rechenoperation 6).
• Der Index der größten Zahl der linken Hälfte ist dann 9 (Rechenoperation 7).
• Wir vergleichen diese Zahl (16) mit der Suchzahl (16) (Rechenoperation 8).

Wir benötigen also acht Rechenoperationen, um die Suchzahl in dem Array zu finden, davon waren vier Operationen logische Vergleiche, und vier Operationen dienten zur Berechnung der Grenzen der jeweiligen Hälften.

Hätten wir die Suchzahl in einer unsortierten Liste der Größe 32 gesucht, hätten wir im Schnitt 16 Vergleiche benötigt (N/2), also doppelt so viel (mindestens).

Vergleichen wir einmal Worst Case- und Best Case-Szenarien für die beiden Suchverfahren und berücksichtigen dabei nur die Vergleichsoperationen.

Lineare Suche:

Best Case = 1 Rechenoperationen,

Worst Case = 32 Rechenoperationen (32 Vergleiche)

Binäre Suche:

Best Case = 2 Rechenoperationen,

Worst Case = 10 Rechenoperationen (5 Vergleiche, 5 Berechnungen)

Eine quantitative Einschätzung der Suchzeit

Bei der binären Suche wird die Anzahl der zu durchsuchenden Elemente bei jedem Suchschritt um 50% reduziert.

Wenn wir einen Array mit 1024 Elementen haben, besteht der erste Schritt in der Bestimmung der Mitte des Arrays und der Entscheidung, ob das Element bereits gefunden wurde bzw. in welcher Hälfte des Arrays man weitersuchen muss.

Der zweite Schritt arbeitet genau so wie der erste, nur die Anzahl der zu durchsuchenden Elemente hat sich auf 512 reduziert (streng genommen auf 511, weil ja nicht nur die eine Hälfte des Arrays wegfällt, sondern auch die Mitte des ursprünglichen Arrays).

Im dritten Schritt müssen nur noch 256 Elemente durchsucht werden, im vierten Schritt 128 und so weiter.

Die Zahl der Suchschritte entspricht also ungefähr dem Zweierlogarithmus der Anzahl der zu durchsuchenden Elemente. Für 1024 Elemente würde man also maximal 10 Suchschritte brauchen, für 10.000 Elemente maximal 14 Schritte.

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

Bei der linearen Suche hatten wir den Zeitaufwand O(N) = N charakterisiert. Bei der binären Suche ist der Zeitaufwand nur noch O(N) = log₂ N, also erheblich geringer.

Nachteil der binären Suche

Auch die binäre Suche ist nicht die schnellste Suche, allerdings ist sie deutlich schneller als die lineare Suche.

Kommen wir noch einmal auf unser Bücher-Beispiel zurück. Wenn Sie nach dem russischen Science Fiction-Autor Isaac Asimov suchen, werden Sie im echten Leben mit Sicherheit nicht in der Mitte des Regals mit der Suche beginnen, sondern am Anfang des Regals, wo die Autoren stehen sollten, deren Nachname mit 'A' beginnt. Die binäre Suche kann also noch erheblich optimiert werden. Damit werden wir uns aber erst im übernächsten Kapitel beschäftigen, der Interpolationssuche und der Indexsuche.

Übungen zur binären Suche

Aufgabe 12.2-2

Eine Schülerin hat ein Flussdiagramm zur binären Suche gezeichnet:

Dieser Entwurf enthält leider noch einige Fehler. Suchen und korrigieren Sie die Fehler, indem Sie ein sauberes und fehlerfreies Flussdiagramm zeichnen, dass die binäre Suche darstellt.

Lösungshinweise...

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

public int suchzeitBinaer(int suchzahl)

Lösungshinweise

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

public int suchzeitBinaerDurchschnitt()

Lösungshinweise: Verfahren Sie ähnlich wie bei der Übung 12.1-5. Auch bei dieser Übung haben Sie zunächst eine Methode geschrieben, welche die Anzahl der Suchschritte ermittelt. Dann haben Sie diese Methode mit verschiedenen zufälligen Zahlen mehrmals ausführen lassen und anschließend die durchschnittliche Suchzeit berechnet.

Durchschnittliche Suchzeit für 50 Zahlen = 5.75
Durchschnittliche Suchzeit für 100 Zahlen = 6.5
Durchschnittliche Suchzeit für 200 Zahlen = 7.5
Durchschnittliche Suchzeit für 400 Zahlen = 8.7
Durchschnittliche Suchzeit für 800 Zahlen = 9.5
Durchschnittliche Suchzeit für 1600 Zahlen = 10.6
Durchschnittliche Suchzeit für 3200 Zahlen = 11.65

Lösungshinweise

Eine binäre Suche benötigt maximal lg₂(N) Vergleiche, auch dann, wenn die Suche erfolglos ist.