Computing mid in Ricerca interpolation?

Question

Sono venuto a sapere che interpolazione Cerca è una modifica del ricerca binaria dove nel binario di ricerca l'ingresso è diviso in due metà uguali in ogni iterazione calcolando

mid = (low + high)/2 

e interpolazione cercare metà è calcolato come

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

Ora ho bisogno di capire questa formula di calcolo mid in cerca di interpolazione.

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

Answer 1

Si può pensare di matrice arr come una funzione f che agisce su indice e restituiscono un valore, che è monotono (a causa di matrice è ordinato). Quindi hai i tuoi dati iniziali f(low) = m e f(high) = M. Ora puoi interpolare la tua funzione f con una linea retta, il che è abbastanza ragionevole da fare perché il tuo f è monotono e hai solo 2 punti. Quindi la vostra interpolazione dovrebbe essere linea (funzione lineare) che passi i punti di lancio (low, m) e (high, M). Questa è la sua equazione

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

Quindi y qui è l'elemento di spazio di ricerca e x è da dominio (x è l'indice di array). Quindi, se la vostra funzione f sarebbe lo stesso come è interpolazione, quindi indice della key sarebbe:

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

Quindi, supponendo che la vostra funzione f è vicino alla sua interpolazione, si deve solo controllare il valore f a x per vedere se è l'obiettivo. Altrimenti si riduce il proprio intervallo di interpolazione.

Answer 2

ampliamento di @JustAnotherCurious risposta

l'equazione perposed da lui si basava su Interpolation Formula (equ di una linea)

Ora, pensate in funzione f() che prende un indice e restituisce il valore dell'asse ,

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.