- Valore cercato
- Ancora possibili
- Confrontate
- Escluse
- Trovate
Ricerca esponenziale
La ricerca esponenziale trova un valore in una lista ordinata in due fasi. Prima guarda le posizioni 1, 2, 4, 8, 16 e così via, raddoppiando ogni volta, fino a trovare un valore non minore del valore cercato. Poi applica la ricerca binaria all'intervallo tra le ultime due posizioni. Scegli il valore da cercare e scopri perché i valori vicini all'inizio si trovano con pochi confronti. 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 segna il valore cercato, e la parte ombreggiata indica dove può ancora trovarsi. La ricerca esponenziale richiede una lista ordinata, quindi una lista non ordinata viene prima ordinata. Scegli il valore, 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
- Scegli il valore da cercare e quante barre usare. Oppure inserisci i tuoi numeri: la ricerca esponenziale li ordina prima.
- 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.
- Cerca un valore vicino all'inizio e uno vicino alla fine, e confronta il conteggio con «Alla ricerca binaria servirebbero».
Come funziona la ricerca esponenziale
Guarda il valore in posizione 1. Se è più piccolo del valore cercato, guarda la posizione 2, poi 4, 8, 16, raddoppiando ogni volta. Appena un valore non è più piccolo, fermati: il valore cercato può trovarsi solo dopo la posizione guardata prima e prima di questa. Applica la ricerca binaria a quell'intervallo. Se il raddoppio supera la fine della lista, applica la ricerca binaria dall'ultima posizione guardata fino alla fine.
Veloce all'inizio, senza conoscere la lunghezza
Per raggiungere un valore in posizione i, il raddoppio richiede circa log₂ i controlli, e l'intervallo trovato contiene meno di i valori, quindi la ricerca binaria ne richiede circa log₂ i in più. In tutto sono circa 2 log₂ i, che dipende da dove si trova il valore cercato, non da quanto è lunga la lista. I valori vicini all'inizio si trovano più in fretta che con la semplice ricerca binaria; quelli vicini alla fine costano fino a circa il doppio. Poiché non ha mai bisogno della lunghezza della lista, funziona anche su liste troppo lunghe da misurare o senza una fine nota.
Domande frequenti
Come funziona la ricerca esponenziale?
Su una lista ordinata controlla le posizioni 1, 2, 4, 8 e così via fino a trovare un valore non minore del valore cercato. A quel punto il valore cercato può trovarsi solo tra le ultime due posizioni controllate, e una ricerca binaria in quell'intervallo lo trova.
La ricerca esponenziale è più veloce della ricerca binaria?
Quando il valore cercato è vicino all'inizio della lista, sì: richiede circa 2 log₂ i confronti per un valore in posizione i, qualunque sia la lunghezza della lista. Quando è vicino alla fine, la semplice ricerca binaria è più veloce, fino a circa il doppio.
A cosa serve?
A cercare in liste di lunghezza sconosciuta o illimitata, come un flusso o una sequenza infinita, e a unire sequenze ordinate, dove la corrispondenza successiva di solito è vicina. La modalità galoppo di Timsort usa la stessa idea del raddoppio.
Perché si chiama esponenziale?
Perché le posizioni controllate crescono in modo esponenziale: 1, 2, 4, 8, 16, ognuna il doppio della precedente. Si chiama anche ricerca per raddoppio o ricerca a galoppo.
I miei numeri vengono inviati da qualche parte?
No. La ricerca avviene 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