| 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
[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]- ^ 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
Voci correlate
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- (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.
