La ricerca lineare (linear search) in Python
In questa lezione implementerai la ricerca lineare per trovare la posizione di un valore in una lista.
Che cos’è la ricerca lineare?
Il problema
A volte i dati non sono ordinati, o ci cerchi una volta sola: una breve lista di nomi, gli ordini di oggi, il primo errore in un log. Ti serve la ricerca più semplice che funziona sempre.
Immaginalo così
La ricerca lineare è come cercare le chiavi in una fila di tasche di cappotti. Controlli la prima tasca, poi la successiva, una per una, e ti fermi appena le trovi. Se arrivi all'ultima tasca, le chiavi non ci sono.
for index, value in enumerate(values):🧥 Controlla ogni tasca in ordineif value == target:🔑 Le chiavi sono qui?return index✅ Trovate: smetti di cercarereturn -1❌ Controllate tutte le tasche: non trovateLa ricerca lineare controlla gli elementi di una collezione uno dopo l'altro finché trova l'obiettivo, richiede fino a O(n) passi ma non ha bisogno di ordinamento.
La ricerca lineare controlla gli elementi dall’inizio finché trova il valore cercato o raggiunge la fine. Non è necessario ordinare prima i dati.
Come funziona l’algoritmo
- Partire dall’indice 0.
- Confrontare l’elemento corrente con il valore cercato.
- Restituire l’indice se coincidono, altrimenti continuare.
- Restituire -1 dopo l’ultimo elemento se non ci sono corrispondenze.
Quando si usa?
- Collezioni non ordinate o piccole.
- Cercare una volta sola, quando ordinare prima costerebbe di più.
- Trovare il primo elemento che rispetta una condizione, non solo un valore esatto.
Quando non serve
- Molte ricerche sugli stessi dati grandi: ordinali una volta e usa la ricerca binaria, o costruisci un set o un dizionario.
- Controllare solo se un valore c'è:
target in valuesfa lo stesso con meno codice.
Visualizzatore di La ricerca lineare (linear search) in Python
O(n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))
Risultato dell'esecuzione
3
Spiegazione del codice
La funzione enumerate() fornisce la posizione e il valore di ogni elemento. Appena trova il valore cercato, la funzione restituisce quella posizione, qui 3. Se arriva in fondo senza trovarlo, restituisce -1. Nel caso peggiore l'algoritmo controlla tutti gli elementi, quindi la complessità è O(n).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi di approfondimento
Prova a modificare il codice seguendo i suggerimenti qui sotto. Cambiare il codice e osservare il risultato ti aiuta a capire molto più che leggerlo soltanto.
- Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
- Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
- Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Errori comuni
Restituire -1 dentro il ciclo
La ricerca si arrende dopo il primo elemento diverso.
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -1
Hai finito questa lezione?
Segnala come imparata per tenere traccia dei tuoi progressi.
Esercitati con una sfida
Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.
- First Negative Index Find where the first negative number appears. Facile
- Minimo dell'Array Trova il valore più piccolo in una lista. Facile