Interpolation search
Ricerca del numero 24 grazie all'algoritmo
Classe	Algoritmo di ricerca
Struttura dati	Array ordinato
Caso peggiore temporalmente	${\displaystyle O(n)}$
Caso ottimo temporalmente	${\displaystyle O(1)}$
Caso medio temporalmente	${\displaystyle log(log(n))}$
Manuale

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 ${\displaystyle log(log(n))}$ confronti (dove ${\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 ${\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;
}

• Ricerca sequenziale
• Ricerca dicotomica
• Hash table

• (EN) Interpolation search, su dcc.uchile.cl.
• (EN) National Institute of Standards and Technology, su nist.gov.
• (EN) Interpolation Search - A Log LogN Search (PDF), su cs.technion.ac.il.

Portale Informatica

Portale Matematica