Controlli
Ancora possibili
Alla ricerca binaria servirebbero

  • Valore cercato
  • Ancora possibili
  • Confrontate
  • Escluse
  • Trovate

Scopri di più sulla ricerca per interpolazione

Ricerca per interpolazione

La ricerca per interpolazione cerca un valore in una lista ordinata come apri un elenco telefonico: per un nome che inizia con T lo apri verso la fine, non a metà. Stima la posizione del valore cercato in base ai valori alle due estremità della parte rimasta. Scegli il valore e la distribuzione, segui i controlli passo dopo passo e scopri quando la stima batte la ricerca binaria e quando no. Premi Avvia per guardare la ricerca, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. La linea tratteggiata indica il valore che cerchi, e la parte ombreggiata mostra dove può ancora trovarsi. La ricerca per interpolazione richiede una lista ordinata, quindi una lista non ordinata viene prima ordinata. Scegli il valore, come sono distribuiti i valori, quante barre usare, oppure inserisci i tuoi numeri. Con l'area selezionata, i tasti freccia avanzano di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scegli il valore da cercare, come sono distribuiti i valori e quante barre usare. Oppure inserisci i tuoi numeri: la ricerca per interpolazione li ordina prima.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della ricerca.
  3. Imposta «Distribuzione» su «Uniforme», «Intervalli casuali» o «Asimmetrica», e confronta «Controlli» con «Alla ricerca binaria servirebbero».

Come funziona la ricerca per interpolazione

Guarda il primo e l'ultimo valore della parte della lista ordinata che può ancora contenere il valore cercato. Se il valore cercato si trova, per esempio, al 40% della distanza tra il primo e l'ultimo valore, controlla la posizione al 40% della lista. Se lì c'è il valore cercato, hai finito. Se il valore è più piccolo, restano solo le posizioni dopo; se è più grande, solo quelle prima. Stima di nuovo in ciò che resta. Se il valore cercato è più piccolo del primo valore o più grande dell'ultimo, non c'è.

Quando la stima funziona

Se i valori sono distribuiti in modo uniforme, come 10, 20, 30 e così via, la prima stima cade sul valore cercato o molto vicino, e in media la ricerca richiede circa log₂(log₂ n) controlli: circa 5 per un miliardo di valori, contro 30 per la ricerca binaria. Se i valori si ammassano, come 1, 2, 3, 4, 1000, le stime continuano a cadere nel posto sbagliato e ogni controllo può escludere un solo valore, quindi il caso peggiore è di n controlli. La ricerca binaria non fa mai peggio di circa log₂ n.

Domande frequenti

Come funziona la ricerca per interpolazione?

Su una lista ordinata stima dove dovrebbe trovarsi il valore cercato in base al primo e all'ultimo valore della parte rimasta, controlla quella posizione e tiene solo la parte dal lato giusto. È come la ricerca binaria, ma con una stima più furba del centro.

La ricerca per interpolazione è più veloce della ricerca binaria?

Con valori distribuiti in modo uniforme sì: in media circa log₂(log₂ n) controlli invece di circa log₂ n. Con valori distribuiti in modo non uniforme può essere molto più lenta, fino a n controlli, mentre alla ricerca binaria non servono mai più di circa log₂ n.

Perché può essere lenta?

Perché la stima presume che i valori crescano in modo uniforme. Se la maggior parte dei valori è piccola e pochi sono enormi, la stima per un valore cercato piccolo cade di continuo vicino all'inizio ed esclude solo uno o due valori ogni volta.

Dove si usa la ricerca per interpolazione?

Dove le chiavi sono distribuite in modo quasi uniforme e i controlli sono costosi, per esempio per cercare record su disco tramite ID numerico o hash. Molti sistemi la combinano con la ricerca binaria per mantenere un buon caso peggiore.

I miei numeri vengono inviati da qualche parte?

No. La ricerca viene eseguita nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor