Home > Informatik > Stufe Q1 > 12. Suchverfahren

12.2 Binäre Suche

Überblick - Lineare Suche - Binäre Suche - Binäre Suchbäume - Index- u. Interpolationssuche

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 ab sofort 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 (rechte Hälfte der linken Hälfte) und machen genau so weiter, bis Sie schließlich ihren Max Frisch gefunden haben.

Eine halb-quantitative Einschätzung der Suchzeit

Binäre Suche in einem Array aus 32 int-Zahlen

Wie immer in der Informatik kommen wir jetzt von der Realität zur Modellbildung. Ein Buch ist eine komplexe Sache, die aus vielen Komponenten besteht. Wir vereinfachen das Problem stark, indem wir einen sortierten Array von int-Zahlen untersuchen.

Gesucht wird die Zahl 13, und wir starten in der Mitte des Arrays bei der Zahl 16. Die Mitte eines Arrays der Länge N kann man relativ leicht finden. Die 13 befindet sich in der linken Hälfte, also können wir die rechte Hälfte komplett ignorieren.

In der linken Hälfte ist die Zahl 8 die Mitte. Die 13 befindet sich in der rechten Hälfte der linken Hälfte, und wieder können wir 8 Zahlen ignorieren.

In der rechten Hälfte der linken Hälfte ist die 12 die Mitte, also müssen wir nur noch die rechte Hälfte der rechten Hälfte der linken Hälfte untersuchen, und die besteht aus nur noch drei Zahlen: 13,14 und 15.

Die Mitte dieser drei Zahlen ist die 14. Da 13 < 14, untersuchen wir jetzt die linke Hälfte der rechten Hälfte der rechten Hälfte der linken Hälfte (kommen Sie noch mit?). Zum Glück besteht diese linke Hälfte nur noch aus einer Zahl, nämlich der 13. Also haben wir endlich die gesuchte Zahl gefunden. 5 Suchschritte waren dafür notwendig. Bei einer linearen Suche hätten wir 13 Suchschritte benötigt, um die Zahl zu finden.

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 der Entscheidung, ob das Element bereits gefunden wurde oder ob man in der linken oder rechten Hälfte des Arrays 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.

Bei der linearen Suche hatten wir den Zeitaufwand O(N) = N charakterisiert. Bei der binären Suche ist der Zeitaufwand nur noch O(N) = log2 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

Übung 12.2-1 (Heft, 7 Punkte)

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

Galdors Entwurf für die binäre Suche

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

Übung 12.2-2 (PC, 7 Punkte)

Erweitern Sie die Klasse Zahlenum eine Methode

public int suchzeitBinaer(int suchzahl)

welche den mit erzeugenSortiert erstellten Array nach der oben beschriebenen Methode des binären Suchens durchsucht und die Zahl der Vergleiche als Wert zurückliefert. Aber bitte nicht mogeln und einfach den Zweierlogarithmus berechnen; es soll die Zahl der tatsächlich benötigten Schritte ermittelt werden.

Lösungshinweise

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

Übung 12.2-3 (PC, 3 Punkte)

Erweitern Sie die Klasse Zahlenaus Übung 12.2-2 um eine Methode

public int suchzeitBinaerDurchschnitt()

welche die in Übung 12.2-3 implementierte Methode 20 mal aufruft. Bei jedem Aufruf wird zunächst eine Zufallszahl zwischen 1 und 1000 "gewürfelt" und dann an suchzeitBinaer übergeben.

Die Rückgabewerte werden addiert und am Ende durch 20 dividiert. Das Ergebnis dieser Division wird dann von der Methode suchzeitBinaerDurchschnitt zurückgegeben.

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.

Übung 12.2-4 (Heft und PC, 5 Punkte)

Erweitern Sie die Klasse Zahlenaus Übung 12.2-3 so, dass die durchschnittliche Suchzeit für verschieden große Arrays automatisch ermittelt und ausgegeben wird. Eine mögliche Ausgabe könnte zum Beispiel so aussehen:

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

Stellen Sie in Ihrem Heft die Abhängigkeit der durchschnittlichen Suchzeiten von der Größe des Arrays graphisch dar und bestimmen Sie, welches Zeitverhalten hier vorliegt (O-Notation, 3 Zusatzpunkte).

Lösungshinweise

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

Seitenanfang -
Weiter mit binären Suchbäumen...