Rechnen in der Interpolationssuche?

Question

kam ich zu wissen, dass Interpolationssuche eine Modifikation von Binäre Suche ist wo in binärer Suche die Eingabe in zwei gleiche Hälften in jeder Iteration geteilt durch

Berechnung

mid = (low + high)/2 

und in Interpolationssuche die Mitte ist berechnet als

mid = low + (key - arr[low]) * ((high - low)/(arr[high] - arr[low])) 

Jetzt muss ich diese Formel verstehen, von mid in Interpolationssuche berechnen.

Ref: https://en.wikipedia.org/wiki/Interpolation_search#Sample_implementation

Answer 1

Sie von Array arr als Funktion denken kann f, die auf Index wirkt und einen Wert zurückgeben, die monoton ist (weil Array sortiert ist). So haben Sie Ihre Ausgangsdaten f(low) = m und f(high) = M. Jetzt können Sie Ihre Funktion f mit einer geraden Linie interpolieren, was ziemlich sinnvoll ist, weil Ihre f monoton ist und Sie nur 2 Punkte haben. So sollte Ihre Interpolation Linie sein (lineare Funktion), die die Wurfpunkte (low, m) und (high, M) übergibt. Das ist es Gleichung

(y - f(low))/(f(high) - f(low)) = (x - low)/(high - low) 

So y hier ist das Element des Suchraumes und x ist von Domain (x Index des Array). Also, wenn Ihre Funktion f wäre das gleiche, wie es Interpolation ist, dann Index Ihrer key wäre:

x = low + (high - low)*(key - f(low))/(f(high) - f(low)) 

Also, vorausgesetzt, dass Ihre Funktion f nahe ist es Interpolation, sollten Sie nur den Wert überprüfen f bei x um zu sehen, ob es das Ziel ist. Andernfalls schrumpfen Sie nur Ihr Interpolationsintervall.

Answer 2

Eine Erweiterung auf @JustAnotherCurious Antwort

die Gleichung von ihm perposed auf Interpolation Formula (EQU einer Linie) beruhte

Nun denken f() als Funktion das nimmt einen Index und gibt seinen y Achsenwert,

zurück

y1 = f(low) 
y2 = f(high) 
x1 = low 
x2 = high 

(y - f(low)) = [(f(high) - f(low))/(high - low)] * (x - low); 

OR 

x = low + [(high - low) * (y - f(low))]/(f(high) - f(low)) 

here: y = key 
we are looking for position(value) of x.