Informazioni su questo esperimento
Cerca lo stesso valore obiettivo con la ricerca lineare e la ricerca binaria affiancate. A ogni passaggio, ciascun algoritmo non ancora terminato esegue un confronto. La ricerca binaria esamina il punto medio dell’intervallo ordinato rimanente; la ricerca lineare avanza di una posizione alla volta. Seleziona un obiettivo dispari per vedere entrambi gli algoritmi terminare senza trovare una corrispondenza.
Obiettivi di apprendimento
- Segui l’intervallo dei candidati e il punto medio nella ricerca binaria
- Confronta il numero di confronti della ricerca lineare e binaria
- Spiega perché la ricerca binaria richiede dati ordinati e come gestisce gli obiettivi assenti
Come si usa
- 1Cerca 32 nell’array predefinito, avanzando di un confronto alla volta.
- 2Nota quando termina la ricerca binaria, quindi continua fino al termine della ricerca lineare.
- 3Scegli un obiettivo dispari, ad esempio 31. Osserva come la ricerca binaria raggiunge un intervallo vuoto.
- 4Modifica la lunghezza dell’array e cerca il suo ultimo valore. Confronta i limiti nel caso peggiore.
Il modello
Ipotesi
- L’array contiene gli interi pari univoci 2, 4, ..., 2n in ordine crescente. Gli indici partono da zero.
- Un confronto tra valori è un singolo confronto a tre vie con il valore obiettivo. I calcoli degli indici e i controlli del ciclo non vengono conteggiati.
- Se il valore obiettivo è assente, la ricerca lineare esamina l’intero array, senza sfruttarne l’ordinamento per interrompersi prima.
- Ogni riga rimane nel proprio stato completato mentre l’altra ricerca continua. L’intervallo dei candidati corrente viene mostrato prima di applicare il risultato del confronto in corso.
Provalo in classe
- Q1Perché la ricerca binaria può scartare metà delle posizioni rimanenti dopo un solo confronto?
- Q2Quanti confronti servono con ciascun metodo per trovare l’ultimo valore in un array di 32 valori?
- Q3Cosa non funziona se si applica la stessa regola del punto medio a un array non ordinato?
Domande frequenti
Perché la ricerca binaria non riesce con un valore obiettivo dispari?
Tutte le voci dell’array sono pari. Un valore obiettivo dispari non può mai corrispondere a una voce, quindi l’intervallo dei candidati alla fine diventa vuoto e l’algoritmo segnala che il valore non è stato trovato.
Perché una riga non si muove più?
Quella ricerca è già terminata. L’esecuzione passo passo continua l’altro algoritmo, così è possibile confrontare i loro costi totali in termini di confronti.