Ricerca lineare in Python: guida per principianti con esempi

Quando si parla di algoritmi di ricerca, la ricerca lineare è uno dei più semplici. Se ti è mai capitato di scorrere un elenco di elementi uno per uno finché non hai trovato ciò che cercavi, allora hai già effettuato una ricerca lineare!

Oltre a essere facile da capire, la ricerca lineare è utile perché funziona su dati non ordinati, a differenza di altri algoritmi di ricerca. Questa versatilità la rende un'opzione valida negli scenari in cui non è possibile ordinare i dati. In questo tutorial userò Python quindi, se prima di iniziare vuoi ripassare Python, dai un'occhiata al percorso di competenze Python Programming.

Cos'è la ricerca lineare?

La ricerca lineare è un algoritmo che individua un valore specifico all'interno di una lista controllando ciascun elemento uno per uno. Parte dal primo elemento, lo confronta con il target e poi continua a scorrere la lista finché non trova il target o raggiunge la fine della lista. È un algoritmo semplice e intuitivo.

La ricerca lineare non ha bisogno che i dati siano ordinati per funzionare, quindi viene usata principalmente su dataset non ordinati. Questo la rende comoda in situazioni in cui ordinare non è pratico o si lavora con dati grezzi. Tuttavia, questo vantaggio ha un costo: non è efficiente quanto altri algoritmi che richiedono dati preordinati.

La ricerca lineare è ideale quando lavori con dataset relativamente piccoli o quando ordinare i dati non è fattibile. Il diagramma qui sotto offre una spiegazione semplificata.

Quando scegliere la ricerca lineare

Vediamo i vantaggi e anche un evidente svantaggio: 

Perché scegliere la ricerca lineare?

A mio avviso, la ricerca lineare ha tre vantaggi distinti:

Quando la semplicità è fondamentale

Uno dei maggiori vantaggi della ricerca lineare è la sua semplicità. L'algoritmo è facile da comprendere e implementare. Non c'è bisogno di preoccuparsi di ordinamenti complessi o di suddividere i dati. Basta partire dall'inizio della lista e controllare ogni elemento finché non trovi quello che cerchi.

Quando non hai tempo di ordinare

A differenza di altri algoritmi di ricerca come la ricerca binaria, la ricerca lineare non richiede che il dataset sia ordinato. È perfetta quando ti serve un modo rapido per trovare qualcosa.

Quando ti serve versatilità

Un altro vantaggio della ricerca lineare è la sua versatilità. Funziona non solo con gli array ma anche con altre strutture dati di Python, come le liste collegate. Finché puoi accedere sequenzialmente agli elementi, la ricerca lineare può fare il suo lavoro. È abbastanza flessibile da gestire diversi tipi di dati, da numeri a stringhe e persino oggetti.

Perché pensarci due volte sulla ricerca lineare?

C'è un aspetto da considerare:

Quando l'efficienza conta

Il principale svantaggio della ricerca lineare è la sua inefficienza, soprattutto con dataset di grandi dimensioni. La sua complessità temporale è O(n), il che significa che nel caso peggiore potresti dover controllare ogni singolo elemento della lista! Questo può rallentare molto se lavori con migliaia o milioni di voci. Per dataset piccoli, però, questa inefficienza può essere trascurabile.

Implementare un algoritmo di ricerca lineare in Python

In Python ci sono due modi comuni per scrivere una ricerca lineare: il metodo iterativo e il metodo ricorsivo. Per mostrare questi due metodi, creiamo prima un semplice dataset di 100 numeri senza duplicati.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]Offerto da

Metodo iterativo

L'approccio iterativo è probabilmente il modo più semplice per capire la ricerca lineare. Si scorre la lista, controllando ogni elemento finché non si trova il target o si raggiunge la fine.

Per prima cosa, creiamo la nostra funzione:

1. Scorriamo ogni elemento della lista arr.

2. Confrontiamo ogni elemento con il target.

3. Se troviamo una corrispondenza, restituiamo l'indice in cui è stato trovato il target.

4. Se terminiamo il ciclo senza trovare il target, restituiamo 1 per indicare che l'elemento non è presente.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundOfferto da

Poi eseguiamo la nostra funzione sul dataset e stampiamo il risultato:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")Offerto da

Eseguendo questo codice, troviamo il valore target al 23° elemento.

Metodo ricorsivo

Il metodo ricorsivo usa una funzione che richiama se stessa per cercare nella lista. Ogni chiamata ricorsiva elabora un elemento alla volta e poi passa al successivo. Questo continua finché non si trova il target o si raggiunge la fine della lista.

Creiamo la nostra funzione ricorsiva:

1. Partiamo controllando il primo elemento (all'indice 0).
2. Se il target corrisponde, restituiamo l'indice.
3. Se il target non corrisponde, richiamiamo ricorsivamente la stessa funzione, ma incrementando l'indice di 1 per controllare l'elemento successivo.
4. La ricorsione continua finché non troviamo il target o raggiungiamo la fine della lista.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementOfferto da

Possiamo usare lo stesso codice di sopra per eseguire questa funzione: restituisce lo stesso indice del nostro target, 23.

Ricorda che questo approccio usa più memoria perché ogni chiamata ricorsiva aggiunge un nuovo livello allo stack delle chiamate. Dai un'occhiata a Understanding Recursive Functions in Python per approfondire la ricorsione.

Complessità temporale e spaziale

Un modo per valutare l'efficienza di un algoritmo è considerare la sua complessità temporale e spaziale. Dai un'occhiata al tutorial Analyzing Complexity of Code through Python per vedere i diversi modi di misurare la complessità di un algoritmo.

Complessità temporale

La complessità temporale di un algoritmo si riferisce a come aumenta il tempo di esecuzione al crescere della dimensione dell'input. La complessità temporale della ricerca lineare è O(n), dove n è il numero di elementi nella lista. Ciò significa che, nel caso peggiore, l'algoritmo potrebbe dover controllare ogni singolo elemento prima di trovare il target (o stabilire che il target non è nella lista). Questo è piuttosto inefficiente, soprattutto per dataset grandi. Ecco perché la ricerca lineare funziona meglio quando abbiamo dataset piccoli, non ordinati, che dobbiamo scorrere una sola volta.

Complessità spaziale

La complessità spaziale di un algoritmo misura quanta memoria richiede al crescere della dimensione dell'input. La complessità spaziale dell'algoritmo di ricerca lineare dipende dal metodo usato. Per il metodo iterativo, la complessità spaziale è O(1), cioè l'algoritmo richiede una quantità costante di memoria, indipendentemente dalla dimensione della lista di input. Questo perché la versione iterativa non richiede memoria aggiuntiva, a parte la lista di input e qualche variabile per tenere traccia dell'indice corrente.

Per il metodo ricorsivo, la complessità spaziale è O(n), cioè la memoria richiesta cresce linearmente con la dimensione della lista di input. Ciò è dovuto alle chiamate ricorsive della funzione, che aggiungono livelli allo stack delle chiamate per ogni elemento della lista. Una lista più grande richiede più memoria per memorizzare tali chiamate, rendendo l'approccio ricorsivo meno efficiente in termini di spazio.

Applicazioni reali della ricerca lineare

Sebbene la ricerca lineare non sia l'algoritmo più efficiente per dataset grandi, ha un utilizzo pratico in molti scenari. Vediamo alcune situazioni in cui la ricerca lineare è lo strumento migliore.

Dataset piccoli in cui ordinare non è pratico

La ricerca lineare è spesso la mia scelta quando ho a che fare con dataset piccoli che non vale la pena ordinare in termini di tempo o risorse. In questi casi, la semplicità della ricerca lineare può essere più efficiente del sovraccarico di ordinare i dati per algoritmi di ricerca più complessi.

Trovare la prima occorrenza di un target

Un altro caso d'uso comune per la ricerca lineare è quando devi trovare la prima occorrenza di un valore target. Poiché la ricerca lineare scorre la lista un elemento alla volta, trova naturalmente la prima istanza del target e ne restituisce la posizione. Questo può essere particolarmente utile, ad esempio, quando cerchi in una stringa la prima comparsa di un carattere.

Quando serve un setup minimo

A volte, la semplicità della ricerca lineare la rende l'opzione migliore. Per esempio, se stai cercando velocemente tra dati che non prevedi di riutilizzare o ti serve una risposta al volo, il setup minimo della ricerca lineare può farti risparmiare tempo.

Ricerca lineare vs. altri algoritmi di ricerca

La ricerca lineare è solo uno dei tanti algoritmi di ricerca. Vediamo altri due algoritmi comuni: la ricerca binaria e la ricerca tramite hash (hash lookup).

Ricerca lineare vs. ricerca binaria

La ricerca binaria è un algoritmo che trova la posizione di un valore target all'interno di un array ordinato dividendo ripetutamente a metà l'intervallo di ricerca. Ha una complessità temporale di O(log n), risultando molto più efficiente della ricerca lineare. Tuttavia, funziona solo su dati ordinati. Quando il dataset è ordinato, la ricerca binaria è quasi sempre la scelta migliore perché dimezza lo spazio di ricerca a ogni passo, riducendo drasticamente il numero di confronti necessari per trovare il target.

La ricerca lineare può essere più appropriata quando i dati non sono ordinati, dato che funziona su qualsiasi dataset, ordinato o meno. Tuttavia, con una complessità di O(n), è molto meno efficiente su dataset ordinati.

Ricerca lineare vs. hash lookup

L'hash lookup è un metodo che usa una tabella hash per trovare rapidamente un elemento. Con una complessità temporale di O(1), è significativamente più veloce sia della ricerca lineare sia di quella binaria. Tuttavia, questa velocità ha un costo: devi prima costruire una tabella hash, che richiede tempo e memoria aggiuntiva. Le ricerche tramite hash funzionano meglio quando devi cercare più volte in dataset grandi, così il setup iniziale si ripaga nel tempo.

Al contrario, la ricerca lineare non richiede alcun setup, rendendola un'opzione più semplice. È la scelta migliore quando devi cercare una sola volta o poche volte, casi in cui il tempo extra per impostare una tabella hash non è giustificabile. La ricerca lineare può anche essere più efficiente in termini di spazio perché non devi memorizzare una tabella hash per usare l'algoritmo.

Errori comuni e come evitarli

Sebbene la ricerca lineare sia un algoritmo semplice, ci sono alcuni errori comuni a cui prestare attenzione.

Errori di uno fuori (off-by-one) nell'iterazione

Uno degli errori più frequenti nell'implementare una ricerca lineare è l'errore di uno fuori. È causato dall'avvio o dall'interruzione dell'iterazione all'indice sbagliato. È importante ricordare che le liste di Python sono indicizzate da zero, quindi il primo elemento ha indice 0. Dimenticarlo può portarti a saltare accidentalmente il primo elemento o a iterare un passo di troppo, causando risultati errati o errori.

Fraintendere l'indice restituito

Un'altra insidia comune è fraintendere cosa restituisce la funzione quando il target non è presente nella lista. Per convenzione, molti algoritmi di ricerca (inclusa la ricerca lineare) restituiscono -1 per indicare che il target non è presente. Alcuni principianti, però, potrebbero pensare che restituisca None, False o qualche altro valore, generando confusione nell'interpretazione dei risultati.

Quando non usare la ricerca lineare

Come detto, la ricerca lineare diventa rapidamente inefficiente per dataset più grandi. Per questo motivo, è meglio riservarla a dataset piccoli, non ordinati, o a ricerche rapide e una tantum.

Conclusione

Essendo uno dei metodi di ricerca più immediati, la ricerca lineare controlla sequenzialmente ogni elemento di una lista, risultando facile da capire e implementare. È una scelta affidabile per ricerche rapide e una tantum su dataset piccoli, soprattutto quando i dati non sono ordinati.

Se ti interessano gli algoritmi di ricerca, dai un'occhiata agli altri miei articoli della serie: Binary Search in Python, Depth-First Search in Python e Breadth-First Search in Python. Potrebbero interessarti anche AVL Tree: Complete Guide With Python Implementation e Introduction to Network Analysis in Python come argomenti più avanzati.