- Valore cercato
- Blocco in esame
- Confrontate
- Escluse
- Trovate
Ricerca a salti
La ricerca a salti sta a metà tra la ricerca lineare e quella binaria. Avanza in una lista ordinata con salti di m posizioni, controllando solo l'ultimo valore di ogni blocco, finché raggiunge un blocco il cui ultimo valore non è più piccolo dell'obiettivo. Poi scorre quel blocco dall'inizio. Scegli il valore e l'ampiezza del salto, e guarda quanti confronti richiedono i salti e la scansione. Premi Avvia per guardare la ricerca, oppure Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto. La linea tratteggiata indica il valore cercato, e la parte ombreggiata è il blocco in esame. La ricerca a salti richiede una lista ordinata, quindi una lista non ordinata viene prima ordinata. Scegli il valore, l'ampiezza del salto, 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, l'ampiezza del salto e quante barre usare. Oppure inserisci i tuoi numeri: la ricerca a salti li ordina prima.
- Premi Avvia, oppure usa Passo e Indietro per procedere un confronto alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della ricerca.
- Con 40 barre, prova un'ampiezza del salto di 2 e di 8, e confronta il numero di confronti con quello di √n.
Come funziona la ricerca a salti
Dividi la lista ordinata in blocchi di m valori. Guarda l'ultimo valore del primo blocco. Se è più piccolo dell'obiettivo, l'obiettivo non può stare da nessuna parte in quel blocco, quindi salta alla fine del blocco successivo e guarda di nuovo. Appena l'ultimo valore di un blocco non è più piccolo, l'obiettivo può stare solo in quel blocco: torna al suo inizio e controlla i suoi valori uno per uno finché trovi l'obiettivo o lo superi.
Scegliere l'ampiezza del salto
Con n valori, i salti richiedono fino a n/m confronti e la scansione fino a m. Salti piccoli rendono la scansione breve ma i salti numerosi; salti grandi fanno il contrario. Il totale n/m + m è minimo quando m = √n, che dà circa 2√n confronti: al massimo 13 per 40 valori, contro 40 per la ricerca lineare e 6 per quella binaria. La ricerca a salti non torna mai indietro di più di un blocco, il che aiuta quando muoversi all'indietro nei dati è lento.
Domande frequenti
Come funziona la ricerca a salti?
In una lista ordinata salta in avanti di m posizioni alla volta e controlla l'ultimo valore di ogni blocco. Quando quel valore non è più piccolo dell'obiettivo, l'obiettivo può stare solo in quel blocco, che poi scorre dall'inizio.
Qual è l'ampiezza del salto migliore?
√n, arrotondato. I salti costano fino a n/m confronti e la scansione fino a m, e la loro somma è minima quando i due sono uguali, per m = √n. Questo dà circa 2√n confronti nel caso peggiore.
La ricerca a salti è più veloce della ricerca binaria?
No, la ricerca binaria richiede meno confronti: circa log₂ n contro circa 2√n. La ricerca a salti può comunque vincere quando tornare indietro nei dati è costoso, perché torna indietro una sola volta, all'inizio di un blocco.
Quale corrispondenza trova quando i valori si ripetono?
La prima. Ogni blocco saltato finisce con un valore più piccolo dell'obiettivo, quindi nessun blocco precedente può contenere una corrispondenza, e la scansione parte dall'inizio del blocco.
I miei numeri vengono inviati da qualche parte?
No. La ricerca gira 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