Home > Informatik > Stufe Q1

12.1 Suchalgorithmen im Überblick

Überblick - Lineare Suche - Binäre Suche - Hashverfahren

Lineare Suche

Die lineare Suche ist das einfachste Suchverfahren überhaupt, im Alltag kommt es sehr häufig vor. Hier ein paar Beispiele:

Sie stehen vor einem Bücherregal, die Bände sind nach Autoren sortiert. Sich suchen nun "Die Physiker", wissen aber nicht, wer das Buch geschrieben hat. Also fangen Sie ganz links oben im Regal an zu suchen und arbeiten sich nach rechts und nach unten voran, bis Sie das Buch entdecken. Oder bis Sie unten rechts am Ende des Regals angekommen sind und das Buch nicht gefunden haben.

Sie sind ein sammelwütiger Zeitschriften-Fan und haben alle möglichen Zeitschriften gekauft und abonniert. Da Sie keine Zeit zum Sortieren hatten, haben Sie die Hefte alle wie sie gekommen sind auf einen großen Stapel gelegt; das neueste Heft liegt oben. Jetzt suchen Sie die Spiegel-Ausgabe, in der ein großer Artikel über Suchalgorithmen steht. Sie arbeiten sich von oben nach unten durch den Stapel, bis Sie das Heft gefunden haben. Sollte das Heft nicht im Stapel enthalten sein, müssen Sie wohl oder übel den gesamten Stapel durchsuchen, bis zum letzten Heft. Erst dann wissen Sie mit 100%iger Sicherheit, dass das Heft nicht im Stapel vorhanden ist.

Kommen wir nun zu einer allgemeinen Definition.

Lineare Suche:

Man fängt beim ersten Element der linearen Datenstruktur an zu suchen und macht so lange weiter, bis man

  • entweder die gesuchten Daten gefunden hat
  • oder
  • am Ende der Datenstruktur angekommen ist und nichts gefunden hat.

Weitere Einzelheiten und Aufgaben zur linearen Suche finden Sie auf der nächsten Seite.

Binäre Suche

Sie stehen wieder vor Ihrem Bücherregal, in dem sich die Bücher alphabetisch nach Autor sortiert befinden. Nun haben Sie gehört, dass Dürrenmatt ("Was einmal gedacht wurde, kann nicht mehr zurück genommen werden") ein toller Autor sein soll, und wollen mal nachschauen, ob Sie ein Buch von Dürrenmatt besitzen.

Natürlich fangen Sie jetzt nicht links oben an zu suchen, bei "A", denn Sie wissen ja, dass die "D"-Autoren weiter rechts im Regal stehen. Also fangen Sie in der Mitte des Regals an, landen bei "M" und merken, dass Sie zu weit nach rechts gegangen sind. Also gehen Sie wieder etwas weiter nach links und sehen die "F"-Autoren. Das ist immer noch zu weit rechts, also gehen Sie wieder ein bisschen nach links und landen schließlich bei "D", und schon sehen Sie Ihren Dürrenmatt. Falls Sie allerdings viele Bücher mit "D"-Autoren haben, müssen Sie mit der Suche weitermachen, und zwar nach dem gleichen Prinzip. Sie schauen zuerst in der Mitte der "D"-Autoren, finden dort zum Beispiel ein Buch von einem gewissen "John Donne" und wissen, dass Sie jetzt wieder weiter rechts suchen müssen.

Dieses Beispiel ist allerdings noch nicht optimal, denn ein etwas intelligenterer Benutzer würde bei der Suche nach "Dürrenmatt" nicht genau in der Mitte des Regals anfangen, sondern gleich in der linken Hälfte, vielleicht in der Mitte der linken Hälfte oder sogar noch etwas weiter links.

Aber das folgende Beispiel zeigt Ihnen eine ganz klassische binäre Suche:

Ihr Freund sagt, dass er eine Zahl zwischen 1 und 1000 hat, und Sie sollen diese Zahl mit möglichst wenigen Fragen erraten. Er sagt Ihnen dann, ob Ihre Ratezahl zu groß oder zu klein ist. Was ist hier die beste Strategie? Natürlich fangen Sie nicht mit der 1 an oder mit der 1000, sondern mit der 500. Wenn die Zahl 500 kleiner ist als die Suchzahl, dann machen Sie mit der 750 weiter. Diese Zahl ist jetzt größer als die Suchzahl. Also nehmen Sie die Mitte zwischen 500 und 750, das wäre die 625. Diese Zahl ist auch größer als die Suchzahl. Sie berechnen jetzt die Mitte zwischen 500 und 625 und kommen auf die 563 (aufgerundet). So machen Sie weiter, bis Sie nach wenigen Versuchen die Zahl gefunden haben.

Binäre Suche

Man fängt in der Mitte einer aufsteigend geordneten Datenstruktur (kleine Schlüssel links, große Schlüssel rechts) an zu suchen. Ist der dort gefundene Eintrag größer als der gesuchte Datensatz, macht man in der Mitte der linken Hälfte weiter. Ist der gefundene Eintrag kleiner als der gesuchte Datensatz, macht man in der Mitte der rechten Hälfte weiter. Entspricht der gefundene Eintrag dem gesuchten Datensatz, kann die Suche erfolgreich abgebrochen werden.

Das Verfahren wird so lange wiederholt, bis entweder der gesuchte Datensatz gefunden wurde oder bis feststeht, dass der Datensatz nicht enthalten ist.

Weitere Einzelheiten und Übungen zur binären Suche finden Sie auf der übernächsten Seite.

Hash-Verfahren

Voraussetzung für dieses Verfahren ist wieder - genau wie bei der binären Suche - dass die Datensätze streng sortiert sind. Ob aufsteigend oder absteigend ist dabei im Prinzip egal.

vier CD-Kästen

Sie haben Ihre CDs schön staubgeschützt in Kästen untergebracht, die Sie auch schön übersichtlich beschriftet haben: "A-B", "C", "D-E", "F-H" und so weiter. Wenn Sie nun eine CD der Gruppe "Cream" suchen, werden Sie nicht in der Mitte der Kastenreihe bei "M-N" anfangen, sondern gezielt zum CD-Kasten mit dem Etikett "C" greifen. In diesem Kasten stehen vielleicht 25 CDs, alphabetisch nach Interpret sortiert. Da können Sie ja zunächst in der Mitte des Kastens schauen und dann in der vorderen oder hinteren Hälfte weitersuchen (binäre Suche).

Hash-Verfahren

Beim Hash-Verfahren (Hashing) wird auf den Suchschlüssel (in unserem Beispiel also der Interpreten-Name) eine Art Berechnungsfunktion angewandt. Das Ergebnis dieser Berechnungsfunktion ist dann die Startadresse der Suche.

In unserem Beispiel haben wir eine ganz einfache Berechnungsfunktion für den Start der Suche: Nimm den Anfangsbuchstaben des Interpreten und suche dann in dem entsprechend beschrifteten Kasten. Bei 1.000 CDs mag das noch gehen, bei 10.000 CDs würde man vielleicht die beiden ersten Buchstaben des Interpreten als Hash-Funktion wählen. Natürlich sind auch kompliziertere Hash-Funktionen denkbar,  aber darauf wollen wir jetzt nicht weiter eingehen.

Weiter mit der linearen Suche...