Ricerca a salti
La ricerca a salti è il modo in cui cerchi una pagina in un libro senza indice: vai avanti un gruppo di pagine alla volta, dando un'occhiata ai numeri di pagina, e quando sei andato troppo oltre sfogli all'indietro l'ultimo gruppo. In una lista ordinata richiede molti meno confronti che controllare ogni valore.
L'idea
In una lista ordinata, l'ultimo valore di un blocco ti dice se l'obiettivo può trovarsi in quel blocco o no: se è più piccolo dell'obiettivo, lo sono anche tutti i valori del blocco. Quindi non serve guardarci dentro. Controlla a turno l'ultimo valore di ogni blocco, saltando interi blocchi, finché ne trovi uno che non è più piccolo dell'obiettivo. Allora l'obiettivo può stare solo in quel blocco: scorrilo dall'inizio.
Un esempio
Cerchiamo 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, con blocchi di 3. Il primo blocco finisce con 8, che è più piccolo, quindi lo si salta. Il secondo blocco finisce con 23, che non è più piccolo, quindi 23 può stare solo in 12, 16, 23. Scorrendolo si trovano 12, 16 e poi 23: trovato dopo 5 confronti, dove la ricerca lineare ne richiede 6 e la ricerca binaria 3. Cercando 40, gli ultimi valori dei blocchi, 8, 23 e 72, portano al blocco 38, 56, 72; 38 è più piccolo e 56 già più grande, quindi 40 non c'è: di nuovo 5 confronti.
Perché √n
Con blocchi di m valori, trovare il blocco giusto richiede al massimo circa n/m confronti e scorrerlo al massimo m. Pochi salti lunghi rendono lunga la scansione; molti salti brevi rendono lunghi i salti. La somma n/m + m è minima quando le due parti sono uguali, per m = √n, dove vale circa 2√n. Per 40 valori significa blocchi di 6 e al massimo 13 confronti; per un milione di valori, blocchi di 1.000 e circa 2.000 confronti.
Dove si colloca
La ricerca binaria richiede meno confronti, circa log₂ n. Ma salta avanti e indietro per tutta la lista, mentre la ricerca a salti va solo avanti e torna indietro una volta, all'inizio di un blocco. Per questo era interessante per dati su nastro o in una struttura collegata, dove tornare indietro è lento. Ben Shneiderman la descrisse come «jump searching» nel 1978. La stessa idea di dividere in blocchi di √n, spesso chiamata decomposizione in radice quadrata, compare in molti altri algoritmi.
Provala
Apri l'app, scegli un valore in Cerca e premi Passo. Ogni salto evidenzia l'ultimo valore di un blocco; i blocchi saltati sbiadiscono, e il blocco che può contenere l'obiettivo è ombreggiato mentre viene scorso. Con 40 barre, cambia Ampiezza del salto da √n a 2 o 8 e guarda come si sposta l'equilibrio tra salti e scansione.
Domande frequenti
Qual è la complessità temporale della ricerca a salti?
O(√n) con blocchi di √n valori: al massimo circa 2√n confronti. Richiede memoria aggiuntiva O(1) e una lista ordinata.
Qual è la differenza tra ricerca a salti e ricerca binaria?
La ricerca binaria dimezza ogni volta la parte rimanente e richiede circa log₂ n confronti, ma si muove avanti e indietro. La ricerca a salti avanza a passi fissi e scorre un blocco, richiede circa 2√n confronti e torna indietro una sola volta.
Nell'ultimo blocco si può usare invece la ricerca binaria?
Sì. Cercare nel blocco con la ricerca binaria riduce la scansione da m confronti a circa log₂ m. I salti costano sempre n/m, quindi conviene usare blocchi più grandi.
La ricerca a salti richiede una lista ordinata?
Sì. Saltare un blocco è sicuro solo perché, se il suo ultimo valore è più piccolo, lo sono anche tutti gli altri. L'app ordina prima una lista non ordinata.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la ricerca a salti