6.1 Allgemeines zum Suchen

Beispiel 1 - Interpolationssuche

Sie stehen vor dem Bücherregal, in dem Sie all die Romane aufbewahren, die Sie seit Jahren gesammelt haben. Die Romane sind alphabetisch nach Autor bzw. Autorin geordnet. Sie wollen nun ein Buch von Karl Melcher lesen. Dann werden Sie sicherlich nicht oben links im Regal bei "A" anfangen zu suchen, aber auch nicht unten rechts bei "Z", sondern werden gezielt irgendwo in der Mitte des Regals mit der Suche anfangen.

Sie haben quasi in Gedanken interpoliert, wo im Regal der beste Einstiegspunkt für Ihre Suche ist.

Beispiel 2 - Indexsuche

Sie befinden sich in der Uni-Bibliothek und suchen ein ganz bestimmtes Buch. Leider kennen Sie nicht den oder die Autoren, sondern nur den Titel des Buches: "Anwendung diverser Suchverfahren im Alltag". Früher hatte man für solche Zwecke Karteikästen. In einem Karteikasten waren die Karteikarten alphabetisch nach Autoren sortiert, in dem anderen Karteikasten hatte man die Karten systematisch nach Fachgebieten sortiert.

Sie gehen also zum Karteikasten mit den Fachgebieten, suchen nach dem Reiter "Informatik" und blättern dann - sequentiell - die Karten durch, bis Sie das gesuchte Buch gefunden haben - oder bis Sie beim nächsten Reiter angekommen sind und frustriert feststellen müssen, dass das Buch nicht in der Bibliothek vorhanden ist.

Aber wir nehmen einmal an, dass Sie die Karteikarte mit dem Buch gefunden haben. Auf der Karteikarte ist dann der Standort (Regal, Fach, Nummer) vermerkt, an dem das Buch steht. Diese Information ist dann Ihr Index. Sie stehen auf, gehen zum Regal und suchen dann - wieder sequentiell - dort nach dem Buch.

Beispiel 3 - Binäre Suche

Sie wollen den Papierkorb Ihres Rechners löschen, das Betriebssystem unterbricht den Löschvorgang aber, weil Sie für irgendeine Datei keine Rechte besitzen.

Sie wollen jetzt diese Datei identifizieren. Sehr zu Ihrem Ärger befinden sich aber 2.600 Dateien im Papierkorb.

Die beste Strategie ist jetzt eine binäre Suche. Sie markieren die ersten 1.300 Dateien und versuchen, diese zu löschen. Wenn es nicht funktioniert, wissen Sie, dass sich die Problemdatei in diesen 1.300 Dateien befindet.

Also markieren Sie jetzt die obere Hälfte dieser Dateien, also die ersten 650. Der Löschversuch gelingt jetzt. Damit wissen Sie, dass sich die problematische Datei in den zweiten 650 Dateien befindet.

Diese halbieren Sie wieder und versuchen, die oberen 325 Dateien zu löschen und so weiter.

Auf diese Weise kommen Sie nach recht wenigen Schritten zur problematischen Datei und können versuchen, diese auf andere Weise zu löschen.

Kleine Kritik an diesem Beispiel:

Handelt es sich bei dem Beispiel 3 wirklich um eine binäre Suche?

Nein, bei einer binären Suche müssen die Daten sortiert vorliegen, was hier nicht der Fall ist. Zwar sind die Dateien irgendwie sortiert, beispielsweise nach Name oder Erstellungsdatum, aber zum Suchen wird diese Sortierung nicht genutzt (Suchkriterium entspricht nicht dem Sortierkriterium).

Vielmehr handelt es sich um das Prinzip des binären Eingrenzens: Wir teilen die Menge und testen, in welcher Hälfte die Problemdatei steckt.

Beispiel 4 - Sequentielle Suche

Sie haben von Ihrem Vater eine große Platten-Sammlung geerbt. Ihr Vater war ein sehr ordentlicher Mensch und hatte seine Platten-Sammlung gut sortiert. Allerdings nicht alphabetisch nach Interpreten, sondern nach dem Kaufdatum.

Sie wollen nun nachschauen, ob auch eine Platte von Ihrer Lieblingsband "The Luftschiff" dabei ist.

Wo fangen Sie an mit der Suche? Sie wissen, dass die ersten Platten dieser Gruppe schon 1984 erschienen sind, also zu der Zeit, als Ihr Vater mit dem Plattensammeln anfing. Aber vielleicht hat er diese Platte auch in den 90er Jahren gekauft oder um 2010 oder erst kurz vor seinem Tod im Jahre 2024.

Es ist also völlig egal, ob Sie ganz vorne oder ganz hinten in der Sammlung mit Ihrer Suche anfangen - aber anfangen müssen Sie ja schließlich.

Obwohl die Plattensammlung hoch geordnet ist, müssen Sie hier eine sequentielle Suche durchführen, da das Ordnungssystem nicht Ihrem Suchkriterium entspricht. Für Ihre Suche ist die Plattensammlung völlig unsortiert.

Hätte Ihr Vater mehrere Register oder Karteikästen angelegt, wäre die Suche kein Problem mehr: Sie suchen im Interpreten-Register nach "The Luftschiff" und finden dort das Kaufdatum. Wenn die Platte im Januar 2010 gekauft wurde, müssen Sie nicht ganz vorn mit der Suche anfangen, aber auch nicht ganz hinten, sondern vielleicht im hinteren Viertel der Sammlung. Dort können Sie dann binär oder sequentiell nach der Platte suchen.