Confronti
Ancora possibili
Alla ricerca lineare servirebbero

  • Valore cercato
  • Ancora possibili
  • Confrontate
  • Escluse
  • Trovate

Scopri di più sulla ricerca binaria

Ricerca binaria

La ricerca binaria trova un valore in una lista ordinata guardando sempre al centro. Se il valore centrale è troppo piccolo, l'obiettivo può stare solo dopo; se è troppo grande, solo prima. In entrambi i casi metà di ciò che resta viene esclusa. Scegli il valore da cercare, segui la ricerca passo per passo e guarda la parte ombreggiata restringersi finché l'obiettivo non viene trovato o non resta nulla. 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 indica il valore cercato, e la parte ombreggiata mostra dove può ancora trovarsi. La ricerca binaria 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

  1. Scegli il valore da cercare e quante barre usare. Oppure inserisci i tuoi numeri: la ricerca binaria li ordina prima.
  2. 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.
  3. Confronta il riquadro Confronti con «Alla ricerca lineare servirebbero», per un valore vicino alla fine o uno che manca.

Come funziona la ricerca binaria

Tieni traccia della parte della lista ordinata che può ancora contenere l'obiettivo; all'inizio è l'intera lista. Guarda il valore al suo centro. Se è uguale all'obiettivo, hai finito. Se è più piccolo, l'obiettivo può stare solo dopo, quindi continua con la parte dopo il centro. Se è più grande, continua con la parte prima. Quando non resta nulla, l'obiettivo non è nella lista.

Perché è così veloce

Ogni confronto dimezza la parte che resta. Partendo da n valori, dopo k confronti ne restano al massimo circa n/2ᵏ, quindi la ricerca finisce dopo al massimo ⌊log₂ n⌋ + 1 confronti: 6 per 40 valori, 10 per 1.000, 20 per un milione. La ricerca lineare può dover guardare ogni valore. Il rovescio della medaglia è che la lista deve essere ordinata, e tenerla ordinata, o ordinarla prima, ha un suo costo.

Domande frequenti

Come funziona la ricerca binaria?

Confronta l'obiettivo con il valore centrale della parte di una lista ordinata che può ancora contenerlo. Se sono uguali, l'ha trovato; altrimenti scarta la metà che non può contenere l'obiettivo e continua nell'altra metà finché lo trova o non resta nulla.

Quanti confronti servono alla ricerca binaria?

Al massimo ⌊log₂ n⌋ + 1 per una lista di n valori: 6 per 40, 10 per 1.000, 20 per un milione. Ogni confronto dimezza ciò che resta.

Perché la ricerca binaria richiede una lista ordinata?

Perché solo in una lista ordinata un confronto ti dice da che parte sta l'obiettivo. In una lista non ordinata un valore più piccolo al centro non dice nulla su dove sia l'obiettivo, quindi non si può escludere niente.

Quale valore trova se ci sono duplicati?

Uno qualsiasi, a seconda di dove cadono i centri. Le varianti che dopo una corrispondenza continuano a cercare a sinistra o a destra trovano la prima o l'ultima occorrenza.

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