Inhalt dieser Seite
Praxisbeispiel Suche im Telefonbuch ↑
Im Prinzip werden sowohl bei der linearen Suche wie auch bei der binären Suche die Suchbegriffe mit den gespeicherten Begriffen verglichen. Bei der linearen Suche vergleicht man den Suchbegriff mit dem ersten Element der Datenstruktur. War die Suche erfolglos, macht man mit dem nächsten Element der Datenstruktur weiter, solange, bis man entweder den Suchbegriff gefunden hat oder bis man das Ende der Datenstruktur erreicht hat.
Ähnlich erfolgt die binäre Suche, nur dass man hier nicht beim ersten Element der Datenstruktur anfängt, sondern bei dem mittleren Element und dann systematisch nach links oder rechts weitersucht. Bei beiden Suchverfahren finden aber jede Menge Vergleiche statt, bei der linearen Suche viele, bei der binären Suche deutlich weniger Vergleiche.
Aber das heißt ja nicht, dass man das binäre Suchen nicht noch weiter optimieren könnte. Schauen wir uns dazu mal ein Praxisbeispiel an.
Suche in einem Telefonbuch
Photo: Ulrich Helmich 2019, Lizenz: Public domain.
Wenn Sie in einem Telefonbuch nach einem Namen wie "Beier" suchen, werden Sie das Buch doch mit Sicherheit nicht genau in der Mitte aufschlagen, sondern ziemlich weit vorne. Ihr Gehirn schätzt ab, wo ungefähr im Buch die B-Einträge stehen. Wenn Sie dann eine Seite aufgeschlagen haben, schauen Sie sich die Namen auf dieser Seite ein. Fangen diese Namen mit "C" oder "D" an, dann wissen Sie, dass Sie zu weit geblättert haben. Vielleicht machen Sie nun tatsächlich eine binäre Suche, indem Sie die Seiten, die Sie in der Hand halten, halbieren und dann gucken, wo sie gelandet sind. Mit der richtigen Hälfte verfahren Sie dann ähnlich, bis Sie die korrekte Seite gefunden haben.
Auch wenn Sie vor einem Bücherregal stehen, in dem die Bücher nach den Autorennamen aufsteigend sortiert sind, werden Sie ähnlich verfahren. Wenn Sie "Tolkien" suchen, werden Sie nicht in der Mitte bei "M" beginnen, sondern schon ziemlich weit rechts schauen. Auch hier führt Ihr Gehirn unbewusst eine Art Berechnung durch, so denn wohl der ideale Einstiegspunkt für Ihre Suche sein könnte.
Und damit wären wir schon bei einem bekannten Suchverfahren, der sogenannten Interpolationssuche. Aber neben der Interpolationssuche gibt es noch viele weitere Suchverfahren, von denen ich auf dieser Seite zwei vorstellen möchte: Zunächst die Sprungsuche, dann die Indexsuche. Ganz am Ende dann die Interpolationssuche.
Sprungsuche ↑
Es gibt mehrere Suchverfahren, die als "Sprungsuche" oder "Jump search" bezeichnet werden können. Wir besprechen zunächst ein Verfahren, wie man es in der Fachliteratur findet.
Sprungsuche mit konstanter Sprungweite
Ein einfaches Verfahren besteht darin, den sortierten Datenbestand in gleich langen Sprüngen zu durchsuchen.
Beispiel:
Sie suchen in einem Array aus 100 Zahlen die Zahl 45.
Der Algorithmus spring zunächst zum Anfang des Arrays, also zu dem Element mit dem Index 0. Die dort stehende Zahl ist aber kleiner als 45.
Jetzt springt die Suche 10 Elemente weiter, also zum Index 10. Auch die dort stehende Zahl ist kleiner als 45.
Als Nächstes wird zum Index 20 gesprungen, dann zum Index 30.
Die Zahl bei Index 40 schließlich ist größer als 45. Damit hat der Algorithmus seinen Zielabschnitt erreicht. Er könnte jetzt ausgehend von Index 40 Schritt für Schritt rückwärts suchen, bis er entweder die Zahl 45 gefunden hat oder bis er auf eine Zahl < 45 stößt. Dann ist klar, dass die 45 nicht in dem Array enthalten ist.
Optimale Sprungweite:
Die optimale Sprungweite m berechnet sich nach m = sqrt(n), wobei n die Zahl der zu durchsuchenden Elemente ist.
Bei einem Array der Größe 1000 wäre die optimale Sprungweite also sqrt(1000) = 32 (gerundet).
Zwei-Ebenen-Sprungsuche:
Bei einem Array der Größe 1.000.000 wäre die optimale Sprungweite m = 1000. Statt jetzt den gefundenen Zielabschnitt linear oder binär zu durchsuchen, bietet sich hierfür eine weitere Sprungsuche an. Man spricht dann von einer Zwei-Ebenen-Sprungsuche.
Anwendung:
Die Sprungsuche mit konstanter Sprungweite eignet sich am besten dann, wenn die Zahlen bzw. zu suchenden Elemente weitgehend gleichmäßig verteilt sind.
Indexsuche ↑
Das Verfahren der Indexsuche soll mithilfe des folgenden Bilds erklärt werden:
Schema zum Jumpsearch
Autor: Ulrich Helmich 2025, Lizenz: Public domain.
Wir sehen hier eine Array aus 29 int-Zahlen, die aufsteigend sortiert sind - von 2 bis 79. Das Bild soll das Prinzip des Index Search verdeutlichen.
Das Verfahren der Indexsuche
Ich erläutere das Verfahren einmal an einem bekannten Beispiel, einem int-Array aus 10.000 aufsteigend sortierten Zahlen im Bereich zwischen 1 und 20.000.
In einem Hilfs-Array werden jetzt bestimmte Indices des Haupt-Arrays gespeichert:
- hilf[0] = Index der ersten Zahl >= 2.000
- hilf[1] = Index der ersten Zahl >= 4.000
- hilf[2] = Index der ersten Zahl >= 6.000
- hilf[3] = Index der ersten Zahl >= 8.000
- hilf[4] = Index der ersten Zahl >= 10.000
- hilf[5] = Index der ersten Zahl >= 12.000
- hilf[6] = Index der ersten Zahl >= 14.000
- hilf[7] = Index der ersten Zahl >= 16.000
- hilf[8] = Index der ersten Zahl >= 18000
Angenommen, wir suchen jetzt die int-Zahl 12.345. Dann würden wir zunächst im Hilfs-Array nachschauen, bei welchem Index die Zahlen >= 12.000 beginnen. Das ist beispielsweise die Position 7.560.
Die eigentliche Suche im Hauptarray beginnt dann bei genau diesem Index. Der Abschnitt umfasst immer noch 2.000 Zahlen, also könnte man hier vielleicht statt einer linearen Suche noch eine einfache binäre Suche einsetzen.
Mehrstufige Indexsuche
Hat man eine noch größere geordnete Sammlung die beispielsweise aus 10 Millionen Datensätzen besteht, legt man zunächst eine Indexdatei mit vielleicht 10.000 Elementen an, in der 10.000 Sprungadressen für die große Sammlung gespeichert sind.
Die Suche kann nun noch beschleunigt werden, wenn man für diese Indexdatei eine Indexdatei 2. Ordnung mit vielleicht 100 Sprungadressen für die 10.000 Element der Indexdatei 1. Ordnung anlegt.
Eine weitere Beschleunigung des Verfahrens findet statt, wenn die Blöcke in der großen Sammlung nicht linear durchsucht werden, sondern nach einem binären Suchverfahren.
Die Interpolationssuche ↑
Wenn die Zahlen bzw. Elemente in dem Hauptarray einigermaßen gleichmäßig verteilt sind, benötigt man keinen Index-Array. Man kann versuchen, die Einstiegsposition für die Suche zu berechnen, zu interpolieren. Daher wird dieses Suchverfahren auch als Interpolationssuche bezeichnet.
30 sehr gleichmäßig verteilte Zahlen
Autor: Ulrich Helmich 2025, Lizenz: Public domain
Wir wollen hier nun nach vier dieser Zahlen suchen und wieder die durchschnittliche Suchzeit berechnen.
In dem Array befinden sich 30 Zahlen im Bereich zwischen 1 und 90. Wenn diese Zahlen einigermaßen gleichmäßig verteilt sind, kann man die Einstiegsposition für die Suche schnell berechnen.
Beispiel: Suche nach der 20
Eine einfache Rechnung ergibt, dass sich die 20 in der Nähe des Index 7 aufhalten muss. Dort befindet sich die 16. Daher wird aufsteigend weitergesucht. Als Nächstes kommt die Zahl 21 - und die ist schon größer als die Suchzahl. Daher kann die Suche bereits nach 2 Vergleichen abgebrochen werden.
Allgemeines Verfahren der Interpolationssuche
Der Algorithmus sucht zunächst nach der kleinsten und nach der größten Zahl im Array.
Aus dem Verhältnis dieser beiden Werte zum gesuchten Wert wird abgeschätzt, an welcher Stelle im Array der gesuchte Wert ungefähr liegen könnte.
An dieser geschätzten Position wird jetzt genauer nachgesehen:
- Suchwert = Wert: Suche ist erfolgreich beendet
- Suchewert < Wert: lineare Suche nach rechts (vorwärts)
- Suchwert > Wert: lineare Suche nach links (rückwärts)
Auch ein rekursives Verfahren ist hier denkbar:
- Suchewert < Wert: lineare Suche rekursiv im linken Teilarray
- Suchwert > Wert: lineare Suche rekursiv im rechten Teilarray
- Solange wiederholen, bis der Wert gefunden wurde oder bis feststeht, dass der Wert nicht enthalten ist.
Praxisbeispiel:
Das wohl bekannteste Praxisbeispiel für eine Interpolationssuche ist die bereits am Anfang dieser Seite beschriebene Suche in einem Telefonbuch. Wenn Sie in einem dicken Telefonbuch beispielsweise der Stadt Hamburg nach einem Namen wie "Wehemeier" suchen, fangen Sie ja auch nicht in der Mitte des Buches an zu suchen, sondern schlagen das Buch gleich weiter hinten auf. Sie schätzen also den Einstieg (den Index) in die Suche ab und ermitteln eine günstige Anfangsposition.