L'interpolation 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 l o g ( l o g ( n ) ) {\displaystyle log(log(n))} confronti (dove n {\displaystyle n} è 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 O ( n ) {\displaystyle O(n)} confronti.[1][2][3]
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 l'upper 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; }