Interpolation search: differenze tra le versioni

Versione delle 14:19, 5 gen 2021

Versione delle 12:24, 6 gen 2021

Riga 16:

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 Olog(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-grande|O]](''n'') 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 ==