Linterpolation search è un algoritmo di ricerca di un dato valore chiave in un array ordinato tramite gli stessi valori delle chiavi. È il metodo corrispondente alla ricerca di un particolare termine all'interno di un dizionario o di un nominativo all'interno di un elenco telefonico.
A ogni passo della ricerca, l'algoritmo valuta dove può trovarsi l'elemento all'interno del search space basandosi sui valori delle chiavi agli estremi dell'array e sul valore da cercare. Dopodiché confronta la chiave selezionata con il valore da cercare. Se si tratta del valore richiesto, allora l'algoritmo è terminato. Altrimenti il search space viene sostituito con la parte restante destra o sinistra dell'array, a seconda del risultato del confronto.
L'interpolation search può essere considerato come una generalizzazione della ricerca dicotomica; quest'ultima, infatti, segue lo stesso procedimento, ma non si basa sui valori degli estremi, bensì taglia il search space sempre a metà.
In media, il costo dell'algoritmo è di confronti (dove è la dimensione dell'array), ma è efficace solo se le chiavi sono distribuite in maniera ragionevolmente uniforme, ovvero se la differenza fra due valori contigui è pressoché costante. Nel caso peggiore (ad esempio, se il valore numerico delle chiavi aumenta esponenzialmente), si avranno confronti.Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison WesleyArmenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley
Esempio di implementazione Il seguente codice C++ è un esempio di semplice implementazione. A ogni passo calcola una possibile posizione del valore, per poi restringere l'intervallo —come nella ricerca binaria — aumentando il lower bound o diminuendo lupper bound.
template <typename T> int interpolation_search(T arr[], int size, T key) { int low = 0; int high = size - 1 ; int mid ;
while (arr[high] != arr[low] && key >= arr[low] && key <= arr[high]) { mid = low + (key - arr[low]) * ((high - low) / ( arr[high] - arr[low]));
if (arr[mid] < key) low = mid + 1 ; else if (key < arr[mid]) high = mid - 1; else return mid;
if (key == arr[low]) return low ; else return -1; }
Note
Voci correlate Ricerca sequenziale Ricerca dicotomica Hash table
Collegamenti esterni
Categoria:Algoritmi di ricerca