Confronti
Corrispondenze
Da controllare

  • Valore cercato
  • Confrontate
  • Escluse
  • Trovate

Scopri di più sulla ricerca lineare

Ricerca lineare

La ricerca lineare è il modo più semplice per trovare un valore: si parte dall'inizio e si controlla ogni valore in ordine finché non salta fuori. Funziona su qualsiasi lista, ordinata o no. Scegli il valore da cercare, avvia la ricerca o procedi un confronto alla volta, e guarda come il costo dipende da dove si trova il valore, o dal fatto che ci sia o no. 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. Scegli il valore, quante barre usare, come partono, oppure inserisci i tuoi numeri. Disattiva «Fermati alla prima corrispondenza» per trovare tutte le corrispondenze. 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, quante barre usare e come partono. Oppure inserisci i tuoi numeri.
  2. 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.
  3. Disattiva «Fermati alla prima corrispondenza» per controllare ogni valore e trovare tutte le corrispondenze.

Come funziona la ricerca lineare

Confronta il primo valore con il valore cercato. Se sono uguali, hai finito. Se no, passa al secondo valore, poi al terzo, e così via. Se arrivi alla fine della lista senza una corrispondenza, il valore cercato non è nella lista. Non c'è niente da preparare: la lista non deve essere ordinata.

Quanti confronti

Un valore in posizione k si trova dopo k confronti. Il caso migliore è un solo confronto, quando il valore cercato è il primo. Il caso peggiore è n, quando è l'ultimo o manca, perché solo dopo aver controllato ogni valore puoi essere sicuro che non c'è. In media, per un valore presente nella lista, ne servono circa (n + 1)/2. Per una lista ordinata la ricerca binaria fa molto meglio: circa log₂ n confronti, 6 invece di un massimo di 40 per 40 valori.

Domande frequenti

Come funziona la ricerca lineare?

Controlla i valori di una lista uno per uno, dal primo all'ultimo, finché trova il valore cercato o finisce i valori. Si chiama anche ricerca sequenziale.

Qual è la complessità temporale della ricerca lineare?

O(n): nel caso peggiore, quando il valore cercato è l'ultimo o manca, lo confronta con tutti gli n valori. In media, per un valore presente nella lista, servono circa (n + 1)/2 confronti.

Quando conviene la ricerca lineare?

Per liste corte, per liste non ordinate in cui si cerca solo una o due volte, e per dati che si possono leggere solo in ordine, come un flusso. Ordinare prima per poter usare la ricerca binaria conviene solo se cerchi molte volte.

Perché un valore assente costa di più?

Perché niente dice alla ricerca lineare di fermarsi prima. Una corrispondenza si può escludere solo controllando ogni valore, quindi un valore che non è nella lista richiede sempre n confronti.

I miei numeri vengono inviati da qualche parte?

No. La ricerca avviene 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