Interpolationssuche

Wenn Sie „Taylor“ im Telefonbuch suchen, schlagen Sie es nicht in der Mitte auf, sondern weit hinten, weil T spät im Alphabet kommt. Die Interpolationssuche macht dasselbe mit Zahlen. Sie schätzt aus der Größe des Zielwerts, wo er stehen sollte, und bei gleichmäßig verteilten Daten ist diese Schätzung erstaunlich gut.

Eine sortierte Reihe von Balken mit einer Linie vom ersten zum letzten Balken; der Zugriff liegt dort, wo die Höhe des Zielwerts diese Linie trifft
Eine sortierte Reihe von Balken mit einer Linie vom ersten zum letzten Balken; der Zugriff liegt dort, wo die Höhe des Zielwerts diese Linie trifft

Die Idee

Die binäre Suche prüft immer die Mitte, egal was sie sucht. Die Interpolationssuche nutzt die Werte. Reicht der verbleibende Teil der Liste von 10 bis 100 und ist der Zielwert 70, liegt er bei zwei Dritteln des Wegs vom ersten zum letzten Wert, also prüft sie bei zwei Dritteln der Strecke. Als Formel liegt der Zugriff bei lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo). Danach behält sie den Teil auf der richtigen Seite, genau wie die binäre Suche, und schätzt erneut.

Zwei Beispiele

In 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 prüft die Suche nach 70 sofort Platz 7: gefunden nach 1 Zugriff, wo die binäre Suche 4 braucht. Nehmen Sie nun 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 und suchen Sie 9. Wegen der 999 landet jede Schätzung nahe am Anfang: Die Suche prüft 1, 2, 3 und so weiter, einen Platz nach dem anderen, und braucht 9 Zugriffe, wo die binäre Suche 3 braucht.

Wie schnell sie ist

Sind die Werte gleichmäßig verteilt oder zufällig aus einer Gleichverteilung gezogen, verkleinert jeder Zugriff den verbleibenden Teil von etwa n auf etwa √n. Das ergibt im Mittel etwa log₂(log₂ n) Zugriffe: rund 5 selbst bei einer Milliarde Werten, gegenüber 30 bei der binären Suche. Sind die Werte sehr ungleichmäßig verteilt, schließt ein Zugriff vielleicht nur einen einzigen Wert aus, und im schlimmsten Fall sind es n Zugriffe, so schlecht wie bei der linearen Suche. Jeder Zugriff kostet außerdem eine Division, daher lohnt sie sich in der Praxis vor allem, wenn Zugriffe teuer sind, etwa Lesevorgänge von der Festplatte.

Geschichte und Varianten

W. W. Peterson beschrieb die Interpolationssuche 1957, um Datensätze auf Speichern mit wahlfreiem Zugriff zu finden. Ihren Mittelwert von log log n bei gleichmäßig verteilten Schlüsseln bewiesen 1978 Perl, Itai und Avni. Praktische Varianten schützen sich vor ungünstigen Daten, indem sie binäre Schritte einstreuen, etwa die interpolierend-sequenzielle oder die interpolierend-binäre Suche, damit der schlimmste Fall nahe bei log n bleibt.

Selbst ausprobieren

Öffnen Sie die App, wählen Sie unter „Suchen nach“ einen Wert und drücken Sie „Schritt“. Jeder Zugriff zeigt, wie weit der Zielwert zwischen den beiden Endwerten liegt und auf welchen Platz das deutet. Stellen Sie „Verteilung“ auf „Gleichmäßig“, und die meisten Suchen enden nach einem Zugriff; stellen Sie sie auf „Schief“, und die Zugriffe kriechen am Anfang der Liste entlang. Die letzte Kachel zeigt, wie viele Schritte die binäre Suche für denselben Wert bräuchte.

Häufig gestellte Fragen

Welche Zeitkomplexität hat die Interpolationssuche?

Im Mittel O(log log n) bei gleichmäßig verteilten Werten und O(n) im schlimmsten Fall. Sie braucht O(1) zusätzlichen Speicher und eine sortierte Liste.

Was ist der Unterschied zwischen Interpolationssuche und binärer Suche?

Die binäre Suche prüft immer die Mitte des verbleibenden Teils. Die Interpolationssuche prüft dort, wo der Zielwert nach den Werten an beiden Enden stehen sollte. Das ist bei gleichmäßig verteilten Werten viel besser und kann bei schiefen viel schlechter sein.

Welche Daten eignen sich für die Interpolationssuche?

Sortierte numerische Schlüssel, die recht gleichmäßig verteilt sind: fortlaufende IDs mit wenigen Lücken, Zeitstempel regelmäßiger Ereignisse oder gehashte Schlüssel. Sie passt zu Daten, bei denen ein Zugriff teuer und etwas Rechnen billig ist.

Warum bietet die App verschiedene Verteilungen?

Weil die Verteilung bestimmt, wie gut die Schätzungen sind. Gleichmäßige Werte lassen die Interpolationssuche fast magisch wirken, schiefe Werte zeigen ihre Schwäche. Der Vergleich mit der Zahl der binären Suche zeigt am klarsten, wann sich welche lohnt.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Interpolationssuche ausprobieren