Ricerca lineare e binaria: algoritmo, codice e complessità

In terza, all’istituto tecnico a indirizzo informatica (ma il discorso vale anche per scienze applicate), dopo cicli e array il programma passa agli algoritmi classici: tra novembre e dicembre si fanno ordinamento e ricerca. La verifica pratica in laboratorio cade tra dicembre e gennaio, cioè tra sei e dieci settimane da oggi. La ricerca binaria è l’algoritmo che in laboratorio si chiede più spesso, perché è corto: sono dodici righe, e basta un < al posto di un <= per rompere tutto.

Qui metto in ordine i due algoritmi di ricerca, la prova a mano con la tabella dei passi (la parte che la prova scritta chiede sempre) e gli errori che vedo nei compiti. Gli ordinamenti li ho trattati a parte in bubble, selection e insertion sort; la notazione $O$ in generale, quella che si fa all’università, è in complessità e O-grande.

Ricerca lineare

Il problema: data una lista e un valore da cercare (il target), dire in che posizione si trova, oppure che non c’è. La ricerca lineare è l’idea più semplice: parto dal primo elemento e li guardo uno alla volta finché trovo il target o finisco la lista. Non richiede nessuna ipotesi sui dati: funziona anche su liste disordinate.

Pseudocodice:

per i da 0 a n-1:
    se lista[i] == target:
        restituisci i
restituisci -1

In Python:

def ricerca_lineare(lista, target):
    for i in range(len(lista)):
        if lista[i] == target:
            return i
    return -1

Convenzione: -1 vuol dire “non trovato”, perché nessuna posizione valida è negativa. Nel caso peggiore (target in ultima posizione o assente) fa $n$ confronti.

Ricerca binaria

La ricerca binaria richiede una condizione precisa: la lista deve essere ordinata. In cambio è molto più veloce. L’idea è quella del gioco “indovina il numero”: guardo l’elemento al centro. Se è il target, ho finito. Se è più piccolo del target, il target può stare solo a destra, quindi scarto la metà sinistra. Se è più grande, scarto la destra. Ripeto sulla metà rimasta.

Servono tre indici: low (primo indice ancora in gioco), high (ultimo indice ancora in gioco) e mid (il centro).

def ricerca_binaria(lista, target):
    low = 0
    high = len(lista) - 1
    while low <= high:
        mid = (low + high) // 2
        if lista[mid] == target:
            return mid
        elif lista[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Riga per riga. high = len(lista) - 1 perché l’ultimo indice valido è uno in meno della lunghezza. Il ciclo continua finché c’è almeno un elemento in gioco, cioè low <= high. // è la divisione intera: se low + high è dispari, mid è il numero arrotondato per difetto. Se lista[mid] è minore del target, il target sta a destra di mid, e proprio per questo si scrive low = mid + 1: mid è già stato escluso. Specularmente high = mid - 1. Quando low supera high la zona in gioco è vuota: il target non c’è.

Versione ricorsiva. Si può scrivere la stessa idea con una funzione che richiama se stessa sulla metà giusta: il caso base è low > high (restituisce -1), il passo ricorsivo chiama la funzione con mid + 1 o con mid - 1.

def ricerca_binaria_rec(lista, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if lista[mid] == target:
        return mid
    if lista[mid] < target:
        return ricerca_binaria_rec(lista, target, mid + 1, high)
    return ricerca_binaria_rec(lista, target, low, mid - 1)

Si chiama con ricerca_binaria_rec(lista, 27, 0, len(lista) - 1). La ricorsione è questione di dicembre-gennaio nella maggior parte delle classi; la ricorsione con fattoriale, Fibonacci e MCD ha la pila delle chiamate spiegata a parte. La versione iterativa è quella da sapere a memoria.

Prova a mano: la tabella dei passi

Prendi la lista ordinata di 10 numeri, con gli indici da 0 a 9:

Cerco 27.

Tre passi. La ricerca lineare, sullo stesso dato, ne avrebbe fatti sei (si ferma all’indice 5).

Cerco 10, che non c’è.

Quattro righe per concludere che non c’è, contro dieci confronti della lineare. In verifica, la tabella si compila con questo ordine fisso: prima low e high, poi mid, poi il valore, poi la decisione. Chi salta una colonna sbaglia l’aggiornamento.

Gli errori che costano punti

• Lista non ordinata. Se i dati non sono ordinati, la ricerca binaria non fallisce con un errore: restituisce una risposta sbagliata, e questo è peggio. Prima di scriverla, controlla che la traccia dica “ordinata”. Altrimenti, o la si ordina prima, o si usa la lineare.
• high = len(lista) invece di len(lista) - 1. È l’errore del “fuori per uno”. Su [1, 2, 3] con target 5, low arriva a $3$ e mid diventa $3$: lista[3] non esiste e Python segnala IndexError.
• Ciclo infinito. Se scrivi low = mid o high = mid senza il $\pm 1$, certe liste non cambiano più: con [1, 3] e target 3, low resta $0$ e mid resta $0$ per sempre. Ogni aggiornamento deve escludere mid.
• while low < high al posto di <=. Con una lista di un solo elemento il ciclo non parte, e un target che si trova proprio sull’ultimo elemento rimasto non viene mai visto.
• Confondere indice e valore. mid è una posizione, lista[mid] è il numero. Si restituisce l’indice, non il valore.
• Restituire -1 dentro il ciclo. Il return -1 va dopo il ciclo, perché si può concludere che il target manca solo quando tutta la lista è stata scartata.

Quanti confronti: $n$ contro ${\log }_{2}n$

Nella lineare, nel caso peggiore, i confronti sono $n$. Nella binaria ogni passo dimezza la lista: dopo un passo ne restano circa $\frac{n}{2}$, dopo due $\frac{n}{4}$, e così via, finché ne resta uno. Il numero di passi è quante volte si può dimezzare $n$, cioè circa ${\log }_{2}n$. Più precisamente, i passi sono al massimo $\lfloor {\log }_{2}n\rfloor +1$, contando un confronto di uguaglianza per passo.

Esempio numerico. Con $n=1000$ elementi: $2^{10}=1024$ è il primo valore di $2^k$ maggiore di $1000$, quindi ${\log }_{2}1000$ vale circa $9,97$, e la binaria fa al massimo 10 confronti. La lineare, nel caso peggiore, ne fa $1000$. Con un milione di elementi la binaria ne fa al massimo $20$ (perché $2^{20}=1048576$), la lineare un milione.

In notazione $O$ si scrive: lineare $O(n)$, binaria $O(\log n)$. La regola per il compito scritto è: “la binaria è molto più veloce, ma solo se la lista è ordinata; e ordinarla costa a sua volta”. Per una singola ricerca su dati disordinati la lineare resta la scelta giusta.

Esercizio 1: contare i passi

Scrivi una versione della ricerca binaria che restituisca sia l’indice trovato sia il numero di passi (cicli) eseguiti. Prova sulla lista [2, 5, 9, 14, 20, 31, 45, 60] (8 elementi) con i target 45, 14 e 1.

def binaria_con_passi(lista, target):
    low, high, passi = 0, len(lista) - 1, 0
    while low <= high:
        mid = (low + high) // 2
        passi += 1
        if lista[mid] == target:
            return mid, passi
        elif lista[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, passi

lista = [2, 5, 9, 14, 20, 31, 45, 60]
print(binaria_con_passi(lista, 45))
print(binaria_con_passi(lista, 14))
print(binaria_con_passi(lista, 1))

Output eseguendo il programma:

(6, 3)
(3, 1)
(-1, 3)

Controllo a mano. Per 45: mid vale $3$ (valore $14$, troppo piccolo), poi $5$ (valore $31$, troppo piccolo), poi $6$ (valore $45$): indice $6$ in $3$ passi. Per 14: mid iniziale è $(0+7)//2=3$ e lista[3] vale proprio $14$: un passo. Per 1: mid vale $3$ ($14>1$), poi $1$ ($5>1$), poi $0$ ($2>1$), poi high diventa $-1$ e il ciclo termina: $3$ passi, risultato -1.

Domanda tipica da verifica: quanti confronti al massimo servono per cercare in $5000$ elementi ordinati? Si cerca la potenza di $2$ giusta: $2^{12}=4096<5000\le 8192=2^{13}$, quindi $\lfloor {\log }_{2}5000\rfloor =12$ e i passi sono al massimo $12+1=13$.

Esercizio 2: trovare l’errore

Il seguente codice dovrebbe cercare target in una lista ordinata. Trova l’errore e correggilo.

def cerca(lista, target):
    low = 0
    high = len(lista)
    while low <= high:
        mid = (low + high) // 2
        if lista[mid] == target:
            return mid
        elif lista[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

L’errore è nella seconda riga: high = len(lista) è un indice che non esiste (l’ultimo valido è len(lista) - 1). Se il target è presente, il codice spesso funziona e l’errore non si vede: cerca([1, 2, 3], 2) restituisce correttamente 1. Ma se il target è maggiore di tutti gli elementi, low cresce fino a coincidere con high, mid diventa len(lista) e Python solleva IndexError: con cerca([1, 2, 3], 5) succede esattamente questo. La correzione è high = len(lista) - 1.

Il piano da qui alla verifica pratica

1. Settimana 1: scrivi la lineare senza guardare, tre volte, poi con while invece di for.
2. Settimana 2: la binaria iterativa, a mano, con la tabella low, high, mid su almeno cinque liste e target diversi (uno presente, uno assente, uno al primo posto, uno all’ultimo, uno che sfora a destra).
3. Settimana 3: scrivila al computer e fai girare i casi limite: lista vuota, lista di un elemento, target agli estremi.
4. Settimane 4-5: la versione ricorsiva e il conteggio dei passi.
5. Prima della prova: ordinamento e ricerca insieme, perché la traccia spesso li combina (“ordina poi cerca”).

Allenarsi e chiedere una mano

Su questo argomento non c’è ancora un simulatore dedicato: per l’informatica la pagina di riferimento è quella delle materie, informatica, dove trovi come lavoro sul programma di indirizzo. Un buon complemento per allenarti sulle strutture di base è il post su cicli e array in terza informatica. Se vuoi una mano prima della prova in laboratorio, scrivimi dai contatti: la diagnosi è gratuita, e partiamo da un tuo programma che non gira, non da una lezione teorica.