Ricerca esponenziale

La ricerca binaria deve sapere dove finisce la lista prima di poter guardare al centro. La ricerca esponenziale no: avanza al galoppo con passi sempre più grandi finché supera il valore cercato, poi applica la ricerca binaria all'ultimo passo. Per questo è ideale per liste di lunghezza sconosciuta, e veloce per i valori vicini all'inizio.

Una fila ordinata di barre con salti che raddoppiano di lunghezza sopra le posizioni 1, 2, 4 e 8, e l'intervallo tra gli ultimi due salti ombreggiato
Una fila ordinata di barre con salti che raddoppiano di lunghezza sopra le posizioni 1, 2, 4 e 8, e l'intervallo tra gli ultimi due salti ombreggiato

L'idea

Controlla il valore in posizione 1, poi 2, 4, 8, 16 e così via, ogni posizione il doppio della precedente. Finché il valore lì è più piccolo del valore cercato, il valore cercato deve essere più avanti. La prima volta che un valore non è più piccolo, il valore cercato è in trappola: si trova dopo la posizione controllata prima e non oltre questa. Quell'intervallo è ordinato, quindi una ricerca binaria trova il valore cercato, o mostra che manca.

Un esempio

Cerca 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. La posizione 1 contiene 2, la posizione 2 contiene 5, la posizione 4 contiene 12, tutti più piccoli. La posizione 8 contiene 56, che è più grande, quindi 23 può trovarsi solo nelle posizioni da 5 a 7. La ricerca binaria controlla quella centrale, la posizione 6, e trova 23: 5 confronti, dove la semplice ricerca binaria ne richiede 3. Cercando 12 nella stessa lista ci si ferma alla posizione 4 dopo 3 confronti, uno in meno della ricerca binaria, e 2 si trova in posizione 1 con un solo confronto.

Quanti confronti

Per un valore in posizione i, il raddoppio si ferma dopo circa log₂ i passi e lascia un intervallo di meno di i posizioni, che la ricerca binaria copre in circa log₂ i passi in più. Quindi la ricerca costa circa 2 log₂ i confronti, qualunque sia la lunghezza della lista. Quando il valore cercato è vicino all'inizio, batte la ricerca binaria, che paga sempre circa log₂ n. Quando è vicino alla fine, la ricerca esponenziale paga fino a circa il doppio. Con 40 valori l'app fa in media circa 3 confronti per le prime cinque posizioni e circa 9 per le ultime cinque, contro circa 4,6 della ricerca binaria.

Lunghezza sconosciuta e galoppo

Jon Bentley e Andrew Yao descrissero questa strategia di raddoppio nel 1976 per la ricerca illimitata: trovare un valore in una sequenza ordinata senza una fine nota, come una lista infinita o un flusso che si può solo sondare. La stessa idea velocizza l'unione. Quando una di due sequenze ordinate continua a vincere, Timsort passa al galoppo: guarda 1, 2, 4, 8 posizioni avanti nell'altra sequenza per trovare dove va il valore successivo, invece di avanzare di una posizione alla volta.

Provala

Apri l'app, scegli un valore in Cerca e premi Passo. Ogni controllo delle posizioni 1, 2, 4, 8 e così via viene evidenziato; appena un valore non è più piccolo, l'intervallo tra le ultime due posizioni viene ombreggiato e subentra la ricerca binaria. Cerca un valore piccolo e poi uno grande, e confronta il conteggio con il riquadro della ricerca binaria.

Domande frequenti

Qual è la complessità temporale della ricerca esponenziale?

O(log i) per un valore in posizione i, quindi al massimo O(log n) per una lista di n valori. Richiede O(1) memoria aggiuntiva e una lista ordinata.

Qual è la differenza tra ricerca esponenziale e ricerca binaria?

La ricerca binaria parte dall'intera lista e ha bisogno della sua lunghezza. La ricerca esponenziale prima trova, raddoppiando, un intervallo che contiene il valore cercato, poi applica la ricerca binaria solo a quell'intervallo. È più veloce quando il valore cercato è vicino all'inizio e funziona senza conoscere la lunghezza.

Perché raddoppiare il passo e non aggiungere una quantità fissa?

Aggiungere un passo fisso è la ricerca a salti, che per attraversare la lista richiede circa n diviso il passo controlli. Raddoppiando si raggiunge la posizione i in circa log₂ i controlli, e l'intervallo che resta non è mai più del doppio del necessario, quindi la ricerca binaria successiva resta breve.

Dove si usa la ricerca esponenziale?

Nella ricerca in dati ordinati illimitati o molto lunghi, nell'unione di sequenze ordinate (il galoppo di Timsort) e nel trovare la prima posizione in cui una condizione diventa vera quando non si conosce un limite superiore.

Pronto a provarlo?

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

Prova la ricerca esponenziale