Ricerca lineare
La ricerca lineare è ciò che fai quando cerchi un nome in una lista non ordinata: parti dall'alto e leggi verso il basso finché non lo trovi. È la ricerca più semplice che ci sia, funziona su qualsiasi lista, e per le liste corte spesso basta.
L'idea
Confronta il valore cercato con il primo valore della lista. Se sono uguali, fermati: il valore cercato è in posizione 1. Altrimenti confrontalo con il secondo valore, poi con il terzo, e così via. Se nemmeno l'ultimo valore corrisponde, il valore cercato non è nella lista. Non serve sapere niente della lista in anticipo: non deve essere ordinata, e i valori possono essere qualsiasi cosa si possa confrontare per uguaglianza.
Un esempio
Cerca 4 in 5, 1, 4, 2, 8. 5 è uguale a 4? No. E 1? No. E 4? Sì: trovato in posizione 3 dopo 3 confronti. Ora cerca 7 nella stessa lista. Ognuno dei cinque valori viene controllato e nessuno corrisponde, quindi dopo 5 confronti la risposta è che 7 non c'è.
Quanti confronti
Per trovare un valore in posizione k servono k confronti. Se il valore cercato ha la stessa probabilità di trovarsi in ogni posizione, sono in media (n + 1)/2 confronti: 20,5 per 40 valori. Un valore assente ne richiede sempre n, perché solo dopo l'ultimo confronto è certo che nessun valore corrisponde. Il costo cresce quindi in proporzione alla lunghezza della lista, e si scrive O(n).
Per cercare più in fretta serve l'ordine
La ricerca lineare non può saltare niente, perché in una lista non ordinata qualsiasi valore può essere ovunque. Quando la lista è ordinata, un confronto dice più di uguale o no: dice da quale parte si trova il valore cercato. La ricerca binaria lo sfrutta per dimezzare la lista a ogni passo e richiede circa log₂ n confronti, al massimo 6 per 40 valori. Però anche ordinare richiede tempo, quindi per una lista in cui si cerca una sola volta la ricerca lineare è spesso la scelta migliore.
Piccoli miglioramenti
Una versione con sentinella mette il valore cercato in fondo alla lista prima di cercare, così il ciclo deve controllare solo se c'è una corrispondenza e non anche la fine della lista. Spostare un valore di un posto in avanti, o in testa, ogni volta che viene trovato rende più economici nel tempo i valori cercati spesso. Nessuno dei due cambia il caso peggiore di n confronti.
Provala
Apri l'app, scegli un valore in Cerca e premi Passo. La linea tratteggiata mostra l'altezza del valore cercato, ogni valore viene evidenziato mentre è controllato e sbiadisce quando è escluso, e una corrispondenza diventa verde. Cerca un valore che non è nella lista per vedere un passaggio completo, oppure disattiva «Fermati alla prima corrispondenza» e scegli Pochi valori distinti per trovare più corrispondenze.
Domande frequenti
Qual è la complessità temporale della ricerca lineare?
O(n) nel caso peggiore e medio, e O(1) nel caso migliore, quando il valore cercato è il primo. Non richiede memoria aggiuntiva.
Qual è la differenza tra ricerca lineare e ricerca binaria?
La ricerca lineare controlla ogni valore in ordine e funziona su qualsiasi lista. La ricerca binaria funziona solo su una lista ordinata, ma a ogni passo dimezza la parte che può contenere il valore cercato, quindi richiede circa log₂ n confronti invece di un massimo di n.
La ricerca lineare richiede una lista ordinata?
No. È il suo vantaggio principale. Su una lista ordinata può fermarsi appena supera la posizione in cui dovrebbe trovarsi il valore cercato, ma resta più lenta della ricerca binaria.
Dove si usa la ricerca lineare?
Ovunque le liste siano corte o non ordinate: trovare un elemento in un piccolo array, scorrere un file o un flusso che si può leggere solo in ordine, o controllare una condizione su ogni elemento. Molte funzioni di libreria, come indexOf in JavaScript e list.index in Python, sono ricerche lineari.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Prova la ricerca lineare