Interpolation search: differenze tra le versioni

Versione delle 20:07, 21 nov 2020

Versione attuale delle 21:23, 1 ott 2024

(4 versioni intermedie di 4 utenti non mostrate)

Riga 1:

{{Algoritmo

|classe = [[Algoritmo di ricerca]]

|immagine =Interpolation sort.gif

|didascalia =Ricerca del numero 24 grazie all'algoritmo

|struttura dati = [[Array]] ordinato

|tempo = <math>O(n)</math>

|tempo migliore = <math>O(1)</math>

|tempo medio = <math>log(log(''n''))</math>

|spazio =

|ottimale =

}}

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]].

AdA 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 <math>log(log(''n''))</math> confronti (dove ''<math>n''</math> è 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 [[<math>O-grande|O]](''n'')</math> confronti.<ref>Weiss, Mark Allen (2006). ''Data structures and problem solving using Java'', Pearson Addison Wesley</ref><ref>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.</ref><ref>Sedgewick, Robert (1990), ''Algorithms in C'', Addison-Wesley</ref>

== Esempio di implementazione ==

Il seguente codice [[C++]] è un esempio di semplice implementazione. AdA ogni passo calcola una possibile posizione del valore, per poi restringere l'intervallo —come nella ricerca binaria—binaria — aumentando il ''lower bound'' o diminuendo l{{'}}''upper bound''.

<syntaxhighlight lang="cpp" line="1">

template <typename T>

int interpolation_search(T arr[], int size, T key)

Riga 53:

== Voci correlate ==

* [[Ricerca sequenziale]]

* [[Ricerca dicotomica]]

* [[Hash table]]

== Collegamenti esterni ==

* {{cita web|http://www.dcc.uchile.cl/~rbaeza/handbook/algs/3/322.srch.p.html|Interpolation search|lingua=en}}

* {{cita web|http://www.nist.gov/dads/HTML/interpolationSearch.html|National Institute of Standards and Technology|lingua=en}}

* {{cita web|http://www.cs.technion.ac.il/~itai/publications/Algorithms/p550-perl.pdf|Interpolation Search - A Log LogN Search|lingua=en}}

{{portalePortale|informatica|matematica}}

[[Categoria:Algoritmi di ricerca]]