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.
6.4.1 Sprungsuche ↑
Man springt im sortierten Array in festen Schritten vorwärts, bis der Block gefunden ist, in dem die Suchzahl liegen muss. Danach durchsucht man nur noch diesen Block linear.
- Vergleich 1 <= 31 = true → 4 Elemente weiter
- Vergleich 9 <= 31 = true → 4 Elemente weiter
- Vergleich 17 <= 31 = true → 4 Elemente weiter
- Vergleich 25 <= 31 = true → 4 Elemente weiter
- Vergleich 33 <= 31 = false → zurück zum vorherigen Block (Index 12+1)
- Ab hier: Lineare Suche
- Vergleich 27 <= 31 = false → 1 Element weiter
- Vergleich 29 <= 31 = false → 1 Element weiter
- Vergleich 31 <= 31 = false → 1 Element weiter
Zeitverhalten O(N), aber deutlich schneller als sequentielle Suche.
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.
Java-Quelltext zur Sprungsuche
public int sprungsuche(int[] a, int suchzahl)
{
if (a == null || a.length == 0)
return -1;
int i = 0;
while (i < a.length && a[i] < suchzahl)
i = i + 5;
int start = i - 5;
if (start < 0)
start = 0;
int ende = i;
if (ende >= a.length)
ende = a.length - 1;
for (int k = start; k <= ende; k++)
{
if (a[k] == suchzahl)
return k;
}
return -1;
}
Nach ein paar Sicherheitsabfragen durchläuft die while-Schleife das zu durchsuchende Array. Wenn die Suchzahl noch nicht gefunden wurde, wird die Laufvariable i um den Wert 5 erhöht - im Array wird also fünf Elemente weiter gesprungen.
Wenn dann ein Array-Element gefunden wird, das nicht mehr kleiner ist als die Suchzahl, wird mit start = i - 5 zum vorherigen Intervall zurückgesprungen.
Es folgen wieder zwei Sicherheitsabfragen, um zu verhindern, dass eine ArrayIndexOutOfBounds-Fehler auftritt.
Dann erfolgt in dem Ziel-Intervall eine einfache sequentielle Suche nach der Suchzahl.
6.4.2 Indexsuche ↑
Man führt ein zusätzliches Index-Array, um schnell den passenden Wertebereich einzugrenzen. Anschließend sucht man nur noch im zugehörigen Teilbereich, meistens linear oder binär oder ebenfalls mit einer Indexsuche. Im letzteren Fall spricht man von einer mehrstufigen Indexsuche.
Beispiel
Beispiel zur Indexsuche
Autor: Ulrich Helmich 03/2026, Lizenz: Public domain
Beschreibung
Oben sehen wir ein kleines Array aus 26 sortierten int-Zahlen im Bereich zwischen 1 und 77.
Darunter ist ein Index-Array gezeigt, dieses besteht aus 8 int-Zahlen. Die Werte dieses Index-Arrays verweisen auf bestimmte Indizes in dem Haupt-Array.
Im Element mit dem Index 1 steht beispielsweise die Zahl 4. Das ist die Position der ersten Zahl im Haupt-Array, die größer oder gleich 10 ist.
An Position 2 im Index-Array steht die Zahl 10. An Index 10 im Haupt-Array befindet sich die erste Zahl >= 20.
Entsprechend sind die Startwerte der nächsten Zehner-Intervalle an den Positionen 3 bis 7 des Index-Arrays gespeichert: 14, 18, 21 und 24
Suchbeispiel
Wir wollen nun die Zahl 44 suchen.
- Wir dividieren 44 durch 10 (ganzzahlig) und erhalten als Ergebnis 4.
- Dann schauen wir im Index-Array an Position 4 nach und sehen dort den Index 14.
- Wir springen in das Haupt-Array an Position 14 und sehen dort die 38. Das ist unser Startpunkt für die eigentliche Suche.
- Die nächste Zahl stimmt bereits mit der Suchzahl überein.
Beispiel 2
In dem zweiten Beispiel wollen wir die Indexsuche auf ein Array anwenden, das aus 10.000 Schlüsselwerten besteht, die im Bereich zwischen 1 und 20.000 liegen und auf die eigentlichen Daten verweisen.
In einem Hilfs-Array werden jetzt bestimmte Indizes des Haupt-Arrays gespeichert:
- hilf[0] = Index der ersten Zahl >= 2.000 ist 1.567
- hilf[1] = Index der ersten Zahl >= 4.000 ist 3.455
- hilf[2] = Index der ersten Zahl >= 6.000 ist 4.678
- hilf[3] = Index der ersten Zahl >= 8.000 ist 4.899
- hilf[4] = Index der ersten Zahl >= 10.000 ist 5.012
- hilf[5] = Index der ersten Zahl >= 12.000 ist 6.301
- hilf[6] = Index der ersten Zahl >= 14.000 ist 6.900
- hilf[7] = Index der ersten Zahl >= 16.000 ist 7.520
- hilf[8] = Index der ersten Zahl >= 18.000 ist 8.910
Angenommen, wir suchen jetzt den Schlüsselwert 12.345. Dann würden wir zunächst im Hilfs-Array nachschauen, bei welchem Index die Zahlen >= 12.000 beginnen. Das ist dann die Position 6.301.
Die eigentliche Suche im Hauptarray beginnt dann bei genau diesem Index. Der Abschnitt umfasst immer ca. 600 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.
Eine Java-Methode zur Indexsuche
private int[] hilfsArrayErzeugen(int[] hauptArray)
{
int[] hilfsArray = new int[11];
int max = ArrayTools.getMaximum(hauptArray);
int intervall = max / 10;
int startwert = intervall;
hilfsArray[0] = 0;
int j = 1;
for (int i = 1; i < hauptArray.length && j < hilfsArray.length; i++)
{
startwert = intervall * j;
if (hauptArray[i] > startwert)
{
hilfsArray[j] = i;
j++;
}
}
return hilfsArray;
}
public int indexsuche(int[] a, int suchzahl)
{
if (a == null || a.length == 0)
return -1;
if (suchzahl < a[0] || suchzahl > a[a.length - 1])
return -1;
int[] indexArray = hilfsArrayErzeugen(a);
int i=1;
while (suchzahl > a[indexArray[i]]) i++;
int start = indexArray[i-1];
int index = ArrayTools.sucheLinearVorwaerts(a, start, suchzahl);
System.out.println("Suchzahl " + suchzahl + " gefunden an Position " + index);
return index;
}
Die erste Methode ist für die Erstellung des Hilfs-Arrays zuständig. Das Haupt-Array wird dabei in zehn Intervalle unterteilt - bei größeren Haupt-Arrays sind natürlich mehr als zehn Intervalle sinnvoll. Insofern ist dieser Quelltext noch nicht universell einsetzbar - das können Sie ja ändern, wenn Sie möchten.
Die Methode hilfsArrayErzeugen() greift dabei auf Hilfs-Methoden der Klasse ArrayTools zu, die wir schon besprochen haben; die Sie aber auch leicht selbst programmieren können.
Die Methode indexsuche() führt dann die eigentliche Suche durch. Nach ein paar Sicherheitsabfragen wird dann zunächst das Hilfs-Array namens indexArray erzeugt. Hier könnte man einwenden, dass dieses Vorgehen noch nicht optimal ist, da das Hilfs-Array bei jedem einzelnen Suchvorgang wieder neu erzeugt wird. Besser wäre es, das Hilfs-Array einmal zu erzeugen und dann für alle folgenden Suchvorgänge zu benutzen.
In der while-Schleife wird dann indexArray nach dem Einstiegspunkt für das Haupt-Array durchsucht. Der gefundene Index wird dann in der Variablen start gespeichert.
Anschließend wird die ArrayTools-Methode sucheLinearVorwaerts() ausgeführt, die ausgehend vom Startindex eine lineare Suche in dem Haupt-Array durchführt und den Index der gefundenen Zahl (oder -1) zurückliefert. Dieser Wert wird dann von der Methode indexsuche() zurückgeliefert.
Die beiden Methoden bieten sicherlich noch Raum für Optimierungen. Das wäre dann eine schöne Aufgabe für die Experten unter Ihnen.
6.4.4 Die Interpolationssuche ↑
Wenn die Zahlen bzw. Elemente in dem Hauptarray einigermaßen gleichmäßig verteilt sind, benötigt man keinen Index-Array. Stattdessen kann man versuchen, die Einstiegsposition für die Suche zu berechnen, also zu interpolieren. Daher wird dieses Suchverfahren auch als Interpolationssuche bezeichnet.
20 sehr gleichmäßig verteilte Zahlen
Autor: Ulrich Helmich 03/2026, Lizenz: Public domain
Grundlegende Berechnungen
Spannweite
Zunächst einmal müssen wir die Spannweite der Werte in dem Array ermitteln. Dazu subtrahieren wir den kleinsten Wert vom größten Wert des Arrays. Bei einem sortierten Array ist das kein Problem, der kleinste Wert steht an Index 0, der größte Wert an Index length-1.
Für unser Beispiel-Array beträgt die Spannweite also: 41 - 1 = 40.
Zahl der Intervalle
Die Zahl der Intervalle ist um 1 kleiner als die Zahl der Arrayelemente. Bei unserem Array haben wir es also mit 19 Intervallen zu tun.
Wertanstieg pro Index
Als Nächstes berechnen wir, wie stark die Werte des int-Arrays von Intervall zu Intervall ansteigen. Dazu dividieren wir die Spannweite durch die Zahl der Intervalle:
40 / 19 = 2,1
Pro Index steigt der Wert der Zahlen um ca. 2,1.
Interpolierter Index
Die Formel für die Berechnung des wahrscheinlichsten Einstiegspunkts in die Suche ist
(Suchzahl - kleinster Wert) / Wertanstieg pro Index
Suchbeispiele
Suche nach der 31
Berechnung der möglichen Position der Suchzahl:
(31 - 1) / 2,1 = 14
Ab Index 14 beginnt dann die lineare Suche. Nach einem Vergleich wird die 31 gefunden
Suche nach der 13:
Berechnung der möglichen Position der Suchzahl:
(13 - 1) / 2,1 = 5.
Suchzahl wird sofort gefunden.
Suche nach der 25:
Berechnung der möglichen Position der Suchzahl:
(25 - 1) / 2,1 = 11
An Index 11 befindet sich die 27 - also wird rückwärts weiter gesucht. Nach einem weiteren Vergleich wird die 25 gefunden.
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 der Stadt Hamburg nach einem Namen wie "Wehemeier" suchen, fangen Sie bestimmt nicht in der Mitte des Buches an, sondern schlagen es gleich weiter hinten auf. Sie schätzen also den Einstieg in die Suche ab und ermitteln eine günstige Anfangsposition.
Auch wenn Sie in einem dicken Hochschul-Lehrbuch im Register nach einem Fachbegriff wie "Binäre Suche" suchen, werden Sie nicht bei "A" oder "Z" anfangen, sondern abschätzen, wo ungefähr die Stichwörter mit "Bi" stehen.
Das Register des berühmten Hollemann/Wiberg, Lehrbuch der Anorganischen Chemie, besteht beispielsweise aus 95 eng bedruckten Seiten. Wenn Sie dort nach "Bleioxid" suchen, werden sich ganz sicher eine Art Interpolationssuche anwenden.