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, Sie haben es bereits angewendet, als Sie in der Vokabelliste (Folge 11) nach einer deutschen Vokabel suchten, um dann die englische Übersetzung auszugeben.

Ihre Algorithmus ist dabei vorne in der Vokabelliste angefangen, also beim Array-Element mit dem Index 0. Dann hat der Algorithmus nach und nach alle Array-Elemente daraufhin untersucht, ob die Deutsch-Komponente mit dem deutschen Suchbegriff übereinstimmt. War das der Fall, brach der Algorithmus die Suche erfolgreich ab und lieferte die Englisch-Komponente der Klasse Vokabel als Ergebnis zurück. War die gesuchte Vokabel nicht in dem Array vorhanden, machte der Algorithmus mit der Suche bis zum Ende des Arrays weiter, um dann eine Fehlermeldung zurück zu liefern, dass die Vokabel nicht in der Liste vorhanden ist.

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

Wenn Sie die Vokabelliste aus Folge 1 bereits nach deutschen Vokabeln sortiert haben, können Sie eine viel intelligentere Such anwenden. Angenommen, Sie suchen die englische Übersetzung des Wortes "Zaun". Würden Sie jetzt bei der Suche vorne in der Liste anfangen? Natürlich nicht. Eine intelligente Suche würde jetzt sogar hinten in der Liste anfangen und sich nach vorne durcharbeiten. Die binäre Suche arbeitet allerdings etwas anders:

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 linken Hälfte weiter. Ist der gefundene Eintrag kleiner als der gesuchte Datensatz, macht man in der rechten Hälfte weiter. Entspricht der gefundene Eintrag dem gesuchten Datensatz, kann die Suche erfolgreich abgebrochen werden.

Das Verfahren wird so lange (rekursiv) 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

Bei der binären Suche wurde bereits erwähnt, dass es noch intelligentere Suchalgorithmen gibt als die binäre Suche. Angenommen, in unserer Vokabelliste sind 100.000 Vokabeln gespeichert und aufsteigend nach dem deutschen Begriff sortiert. Wenn Sie nach der Übersetzung von "Algorithmus" suchen, würde eine intelligente Suche am Anfang des Arrays beginnen. Bei der Suche nach "Zebra" würde diese Suche am Ende des Arrays beginnen. Wird das Wort "Mitte" gesucht, würde die Suche irgendwo in der Mitte des Arrays anfangen.

Hash-Verfahren beruhen darauf, dass vor dem eigentlichen Beginn der Suche berechnet wird, wo der beste "Einstieg" in die Suche ist. Bei 100.000 sortierten Vokabeln könnte man beispielsweise in einem Extra-Durchgang nachschauen, bei welchem Index die erste Vokabel mit dem Anfangsbuchstaben 'B' vorkommt, bei welchem Index das erste Wort mit dem Anfangsbuchstaben 'C' steht und so weiter bis 'Z'. Man würde dann eine Tabelle wie zum Beispiel diese erhalten:

Eine einfache Hashtabelle mit den Indices der Anfangsbuchstaben des Arrays

Hilfreich zum Verständnis eines solchen Hash-Verfahrens ist auch das folgende Bild:

Eine Liste mit Zeigern auf die Anfangsbuchstaben der Vokabelliste

Oben im Bild ist der Array mit den 100.000 Einträgen zu sehen. Aus technischen Gründen konnte hier nur ein Bruchteil der Array-Elemente gezeigt werden.

Unten im Bild sieht man einen zweiten Array, der aus genau 26 Elementen besteht. Jedes Array-Element speichert die Startadresse des jeweiligen Buchstaben im oberen Array. Dieser Index-Array entspricht somit der Tabelle in der Abbildung weiter oben.

Bei 100.000 oder mehr Array-Elementen ist ein Index-Array mit nur 26 Elementen vielleicht auch noch zu klein für eine schnelle Suche. Man könnte dann einen Index-Array mit 26 x 26 Elementen anlegen, um die Anfangspositionen der Buchstabenpaare "Aa", "Ab", Ac", ... "Zx", Zy", "Zz" zu speichern.

Eine richtige Berechnung würde bei diesen Verfahren allerdings noch nicht durchgeführt. Man würde in einem Vorlauf-Prozess die Anfangsadressen der Anfangsbuchstaben oder Paare von Anfangsbuchstaben ermitteln und in dem Index-Array speichern.

"Richtige" Hash-Verfahren berechnen die Einsprungadresse dagegen. Wenn der Vokabel-Array 100.000 Elemente umfasst und man das Wort "Hash-Verfahren" sucht, kann man folgendermaßen vorgehen:

"H" ist der 8. Buchstabe des Alphabets. Wenn man die Zahl 100.000 durch 26 dividiert, erhält man die Zahl 3846. Das heißt, die Wahrscheinlichkeit, dass Worte mit dem Anfangsbuchstaben "B" bei Index 3846 beginnen, ist recht groß. Entsprechend sollten Begriffe mit dem Anfangsbuchstaben "H" bei Index 30.769 beginnen.

Die Suche nach "Hash-Verfahren" startet also bei Index 30.796. Nun ist die Wahrscheinlichkeit sehr klein, dass das Wort bei diesem Index sofort gefunden ist.

Ist das Wort an Position 30.796 größer als "Hash-Verfahren", so arbeitet man sich nach links durch, bis man das Wort gefunden hat oder bis man ein Wort gefunden hat, das kleiner ist als das Suchwort.

Ist das Wort an Indx 30.796 kleiner als das Suchwort, so sucht man rechts weiter, bis man das Wort gefunden hat oder bis man ein Wort gefunden hat, das größer ist als das Suchwort.

Hash-Verfahren

Beim Hash-Verfahren (Hashing) wird auf den Suchschlüssel (in unserem Beispiel also die Deutsch-Komponente der Vokabel) eineBerechnungsfunktion angewandt. Das Ergebnis dieser Berechnungsfunktion ist dann die Startadresse der Suche.

Informatik-Abitur NRW

Nachdem ich diese Seite neu geschrieben habe, interessiert es mich doch, ob das Thema "Hash-Verfahren" überhaupt eine Rolle im Informatik-Zentralabitur NRW spielt. Ich durchsuche einmal meine Festplatte mit sämlichen Abiturvorschlägen seit 2007 nach dem Suchwort "Hash".

Das Ergebnis ist ernüchternd: 0 Objekte wurden gefunden.

Der Suchbegriff "binäre Suche" wurde in den Abiturvorgaben von 2009 und 2010 gefunden, bei den inhaltlichen Schwerpunkten. In den Vorgaben 2018 taucht das Stichwort "Suche" nicht ein einziges Mal auf. Schauen wir uns mal den Kernlehrplan Informatik an. Dort steht auf Seite 23 tatsächlich beim Inhaltsfeld Algorithmen: "Algorithmus zum Suchen und Sortieren":

Screenshot vom Kernlehrplan NRW zum Thema 'Algorithmen zum Suchen und Sortieren'

Wie man auf dieser Abbildung gut sehen kann, spielen Sortierverfahren eine deutlich größere Rolle für das Abitur NRW als Suchverfahren.

Weiter mit der linearen Suche...