Ricerca in interpolazione
La ricerca per interpolazione è un algoritmo di ricerca in un array ordinato.
Principio
Il principio è simile a quello della ricerca dicotomica : implica il confronto di un elemento dell'array con il valore cercato, quindi la ricerca ricorsiva nella parte rilevante dell'array. La differenza sta nella scelta del valore del tavolo scelto. In una ricerca dicotomica, viene utilizzata la mediana. Questa scelta non è ottimale se sappiamo che i valori sono “ben distribuiti”, ad esempio per cercare la parola “banana” in un dizionario, è più rilevante cercare all'inizio del dizionario. Quindi nella ricerca per interpolazione, è la posizione che corrisponde al luogo dell'elemento cercato, se i dati fossero regolarmente spaziati tra il minimo e il massimo della (sotto) tabella, che viene studiata.
Complessità
Se i valori della tabella sono determinati su una legge uniforme , la ricerca ha una complessità temporale in media di .
Storia
L'algoritmo è stato presentato da W Wesley Peterson, in un articolo del 1957.
Note e riferimenti
- “ algoritmi di ricerca di base ” , a EPITA .
- Yehoshua Perl, Alon Itai e Haim Avni, " Interpolation search - a log log N search, " Communications of the ACM , vol. 21, n o 7, 1978, p. 550-553
- Andersson, Arne e Mattsson, Christer, " Dynamic Interpolation Search in o (log log n) Time ", Automata, Languages and Programming , 1993, p. 15-27
- W Wesley Peterson, " Addressing for random-access storage " , IBM journal of Research and Development , vol. 1, n o 2 1957, p. 130-146.
Vedi anche
Articolo correlato
- Ricerca sequenziale , un altro tipo di ricerca
Link esterno
- Jean-Michel Léry, " ricerca per interpolazione in" Algorithmics in C " "