Interpolation search

Interpolation search
Classe	Algoritmo di ricerca
Struttura dati	Array ordinato
Caso peggiore temporalmente	n
Caso ottimo temporalmente	1
Caso medio temporalmente	log(log(n))

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.

Ad 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 log(log(n)) confronti (dove 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) confronti.^[1]^[2]^[3]

Esempio di implementazione

Il seguente codice C++ è un esempio di semplice implementazione. Ad 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;
}

Note

^ Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
^ Armenakis, 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