- Zielwert
- Noch möglich
- Verglichen
- Ausgeschlossen
- Gefunden
Interpolationssuche
Die Interpolationssuche sucht einen Wert in einer sortierten Liste so, wie Sie ein Telefonbuch aufschlagen: Für einen Namen mit T schlagen Sie weit hinten auf, nicht in der Mitte. Sie schätzt den Platz des Zielwerts aus den Werten an beiden Enden des verbleibenden Teils. Wählen Sie den Wert und die Verteilung, gehen Sie die Zugriffe Schritt für Schritt durch und sehen Sie, wann die Schätzung die binäre Suche schlägt und wann nicht. Drücken Sie „Abspielen“, um die Suche anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die gestrichelte Linie markiert den gesuchten Wert, und der schattierte Teil zeigt, wo er noch sein kann. Die Interpolationssuche braucht eine sortierte Liste, daher wird eine unsortierte Liste zuerst sortiert. Wählen Sie den Wert, die Verteilung der Werte und die Anzahl der Balken, oder geben Sie eigene Zahlen ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie den gesuchten Wert, die Verteilung der Werte und die Anzahl der Balken. Oder geben Sie eigene Zahlen ein: Die Interpolationssuche sortiert sie zuerst.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Schritt nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Suche zu springen.
- Stellen Sie „Verteilung“ auf „Gleichmäßig“, „Zufällige Lücken“ oder „Schief“ und vergleichen Sie „Zugriffe“ mit „Binäre Suche bräuchte“.
So funktioniert die Interpolationssuche
Betrachten Sie den ersten und letzten Wert des Teils der sortierten Liste, der den Zielwert noch enthalten kann. Liegt der Zielwert etwa bei 40 % des Wegs vom ersten zum letzten Wert, prüfen Sie den Platz bei 40 % der Strecke. Ist der Wert dort der Zielwert, sind Sie fertig. Ist er kleiner, bleiben nur die Plätze danach; ist er größer, nur die Plätze davor. Schätzen Sie im Rest erneut. Ist der Zielwert kleiner als der erste Wert oder größer als der letzte, ist er nicht enthalten.
Wann die Schätzung funktioniert
Sind die Werte gleichmäßig verteilt, etwa 10, 20, 30 und so weiter, landet die erste Schätzung auf dem Zielwert oder ganz nah daran, und die Suche braucht im Mittel etwa log₂(log₂ n) Zugriffe: rund 5 bei einer Milliarde Werten, gegenüber 30 bei der binären Suche. Ballen sich die Werte, etwa 1, 2, 3, 4, 1000, landen die Schätzungen immer wieder an der falschen Stelle, und jeder Zugriff schließt vielleicht nur einen Wert aus. Im schlimmsten Fall sind es also n Zugriffe. Die binäre Suche ist nie schlechter als etwa log₂ n.
Häufig gestellte Fragen
Wie funktioniert die Interpolationssuche?
In einer sortierten Liste schätzt sie aus dem ersten und letzten Wert des verbleibenden Teils, wo der Zielwert stehen sollte, prüft diesen Platz und behält nur den Teil auf der richtigen Seite. Sie ist wie die binäre Suche, nur mit einer klügeren Schätzung als der Mitte.
Ist die Interpolationssuche schneller als die binäre Suche?
Bei gleichmäßig verteilten Werten ja: im Mittel etwa log₂(log₂ n) Zugriffe statt etwa log₂ n. Bei ungleichmäßig verteilten Werten kann sie viel langsamer sein, bis zu n Zugriffe, während die binäre Suche nie mehr als etwa log₂ n braucht.
Warum kann sie langsam sein?
Weil die Schätzung annimmt, dass die Werte gleichmäßig wachsen. Sind die meisten Werte klein und einige riesig, landet die Schätzung für einen kleinen Zielwert immer wieder nahe am Anfang und schließt jedes Mal nur ein oder zwei Werte aus.
Wo wird die Interpolationssuche eingesetzt?
Wo Schlüssel annähernd gleichmäßig verteilt und Zugriffe teuer sind, etwa beim Nachschlagen von Datensätzen nach numerischer ID oder Hash auf der Festplatte. Viele Systeme kombinieren sie mit der binären Suche, um einen guten schlimmsten Fall zu behalten.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Suche läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor