Interpolation search: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Aggiunto una gif dell'algoritmo e la relativa didascalia nel template "Algoritmo" |
m →top: clean up, replaced: L'''' → L{{'}}''' |
||
Riga 10:
|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]].
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.
| |||