Interpolation search: differenze tra le versioni

Versione delle 23:52, 6 gen 2016

Versione delle 23:37, 11 gen 2017

Riga 12:

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

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