Ricerca binaria in Python
La ricerca binaria dimezza l’intervallo rimasto a ogni confronto.
Che cos’è Ricerca binaria?
La ricerca binaria dimezza l’intervallo rimasto a ogni confronto.
Trova un valore in una lista ordinata.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Visualizzatore di Ricerca binaria in Python
O(log n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
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))Output previsto
3Come funziona
Il valore centrale decide quale metà conservare. Tempo O(log n); l’input deve essere ordinato.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.