La ricerca binaria (binary search) in Python
In questa lezione implementerai la ricerca binaria per trovare velocemente un valore in una lista ordinata.
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.
low, high = 0, len(values) - 1📖 Le pagine in cui devi ancora cercaremiddle = (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à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
lowehighsegnano la parte della lista che può ancora contenere l'obiettivo.middle = (low + high) // 2sceglie l'indice centrale di quella parte.- Se
values[middle] < target, l'obiettivo è a destra, quindilow = middle + 1; altrimentihigh = middle - 1. while low <= high:si ferma quando l'intervallo è vuoto, e la funzione restituisce-1per non trovato.- 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:
ino 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
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))
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.
- 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
Usare < invece di <= nel ciclo
Con low < high, un obiettivo nell'ultima posizione rimasta non viene mai controllato.
while low < high:
while low <= high:
Non andare oltre il centro
low = middle può ripetere lo stesso centro all'infinito.
low = middle
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.
- Tempo di Produzione in Fabbrica Trova il tempo minimo in cui macchine parallele possono completare un numero target di oggetti. Media
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Difficile