Algoritmi Python

La ricerca lineare (linear search) in Python

In questa lezione implementerai la ricerca lineare per trovare la posizione di un valore in una lista.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

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.

Dal controllo delle tasche al codice
for index, value in enumerate(values):🧥 Controlla ogni tasca in ordine
if value == target:🔑 Le chiavi sono qui?
return index✅ Trovate: smetti di cercare
return -1❌ Controllate tutte le tasche: non trovate
Controlla un elemento alla volta; fermati alla prima corrispondenza.
In una frase

La 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

  1. Partire dall’indice 0.
  2. Confrontare l’elemento corrente con il valore cercato.
  3. Restituire l’indice se coincidono, altrimenti continuare.
  4. Restituire -1 dopo l’ultimo elemento se non ci sono corrispondenze.
Complessità: Tempo O(n) nel caso medio e peggiore, con spazio aggiuntivo O(1).

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 values fa 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

Esegui codice →
main.py
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))
Crea un pulsante Run per questo esempio

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.

  1. Prova con una lista vuota, una lista di un solo elemento e una lista con valori ripetuti.
  2. Stampa lo stato dopo ogni passo per vedere l'algoritmo al lavoro.
  3. Misura il tempo con 100, 1.000 e 10.000 elementi e confrontalo con un'altra soluzione.
Esegui nel compilatore Python →

Errori comuni

Restituire -1 dentro il ciclo

La ricerca si arrende dopo il primo elemento diverso.

Problema
for index, value in enumerate(values):
    if value == target:
        return index
    return -1
Correzione
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.

Tutte le sfide