Für diejenigen von Ihnen, die mit der Interpolationssuche nicht vertraut sind, ist es eine Methode, in einem sortierten Array nach einem Wert zu suchen, der möglicherweise schneller ist als die binäre Suche. Sie betrachten das erste und das letzte Element und interpolieren (unter der Annahme, dass der Inhalt des Arrays gleichmäßig verteilt ist) linear, um die Position vorherzusagen.

Zum Beispiel: Wir haben ein Array der Länge 100 mit array [0] = 0 und array [99] = 99. Wenn wir nach 80 suchen, ist es intuitiv, Array [80] über Array [50] zu testen, und wenn das Array nahezu gleichmäßig verteilt ist, wird die erwartete Laufzeit auf @ reduzierlog(log(N))

Für Zahlen wird der zu überprüfende Ort durch die folgende Gleichung definiert:low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low]).

Ein häufiges Beispiel, das verwendet wird, um die intuitive Art der Interpolationssuche zu demonstrieren, ist: Stellen Sie sich vor, Sie versuchen, das Wort 'gelb' in einem Wörterbuch zu finden. Sie würden nicht die binäre Suche verwenden und zum halben Weg gehen. Sie würden eher zum erwarteten Ort gehen.

Humans kann Strings natürlich linear interpolieren, aber ich kann nicht herausfinden, wie es sich codiert. Wie interpolieren wir Strings linear?