Algoritmi Python

La ricerca binaria (binary search) in Python

In questa lezione implementerai la ricerca binaria per trovare velocemente un valore in una lista ordinata.

  • Intermedio
  • 2 min di lettura
  • 1 esempio eseguibile

Introduzione

Il problema

Cercare un valore in una lista di un milione di elementi controllandoli uno per uno può richiedere un milione di confronti. Quando la lista è ordinata puoi fare molto meglio: bastano circa 20 confronti, perché ogni controllo esclude metà di ciò che resta.

Immaginalo così

La ricerca binaria è il modo in cui cerchi una parola in un dizionario di carta. Lo apri a metà, guardi se la tua parola viene prima o dopo quella pagina e butti via la metà che non può contenerla. Ripeti con la metà rimasta finché arrivi alla parola.

Dal dizionario di carta al codice
low, high = 0, len(values) - 1📖 Le pagine in cui devi ancora cercare
middle = (low + high) // 2👆 Apri a metà
low = middle + 1➡️ La parola viene dopo: scarta la prima metà
high = middle - 1⬅️ La parola viene prima: scarta la seconda metà
Ogni confronto dimezza ciò che resta, quindi anche liste enormi richiedono pochi passi.
In una frase

La ricerca binaria trova un valore in una lista ordinata confrontandolo ripetutamente con l'elemento centrale e scartando la metà che non può contenerlo, in O(log n) passi.

Punti chiave

  1. low e high segnano la parte della lista che può ancora contenere l'obiettivo.
  2. middle = (low + high) // 2 sceglie l'indice centrale di quella parte.
  3. Se values[middle] < target, l'obiettivo è a destra, quindi low = middle + 1; altrimenti high = middle - 1.
  4. while low <= high: si ferma quando l'intervallo è vuoto, e la funzione restituisce -1 per non trovato.
  5. Per 17 la ricerca controlla 12, poi 25, poi 17: tre confronti invece di quattro.

Quando si usa?

  • Cercare in grandi dati ordinati: ID, dizionari, log ordinati.
  • Trovare dove inserire un valore perché una lista resti ordinata.
  • Giochi di indovinelli e qualsiasi problema in cui la risposta si può restringere con più alto o più basso.

Quando non serve

  • I dati non sono ordinati: ordinare solo per cercare una volta costa più di una ricerca lineare.
  • Liste piccole o ricerche isolate: in o un dizionario è più semplice; per molte ricerche per chiave, un dict o un set è ancora più veloce.

Visualizzatore di La ricerca binaria (binary search) in Python

O(log n)

Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.

Codice di esempio

Esegui codice →
main.py
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([3, 8, 12, 17, 25, 31], 17))
Crea un pulsante Run per questo esempio

Risultato dell'esecuzione

3

Spiegazione del codice

Le variabili low e high indicano l'intervallo di ricerca rimasto. Se l'elemento centrale è minore del valore cercato, l'algoritmo scarta la metà sinistra con low = middle + 1, altrimenti scarta quella destra. La complessità è O(log n), a patto che la lista in ingresso sia già ordinata.

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

Usare < invece di <= nel ciclo

Con low < high, un obiettivo nell'ultima posizione rimasta non viene mai controllato.

Problema
while low < high:
Correzione
while low <= high:

Non andare oltre il centro

low = middle può ripetere lo stesso centro all'infinito.

Problema
low = middle
Correzione
low = middle + 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