Interpolation search

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Interpolation search
ClasseAlgoritmo di ricerca
Struttura datiArray ordinato
Caso peggiore temporalmenten
Caso ottimo temporalmente1
Caso medio temporalmentelog(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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  1. ^ Weiss, Mark Allen (2006). Data structures and problem solving using Java, Pearson Addison Wesley
  2. ^ 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.
  3. ^ Sedgewick, Robert (1990), Algorithms in C, Addison-Wesley

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]