Algoritmo di ricerca binaria Python
Cerca elenchi ordinati in tempo logaritmico O(log n). Esegui e comprendi la ricerca binaria in Python, inclusa la logica passo passo, i casi limite e le ottimizzazioni.
Panoramica
La ricerca binaria è un algoritmo eccezionalmente efficiente per trovare un elemento in un elenco ordinato. A differenza della ricerca lineare che analizza ogni elemento in sequenza in tempo O(n), la ricerca binaria funziona dividendo ripetutamente l'intervallo di ricerca a metà.
La ricerca inizia esaminando l'elemento centrale dell'array. Se il valore di destinazione corrisponde all'elemento centrale, viene restituita la sua posizione. Se il target è più piccolo, l'algoritmo restringe la ricerca alla metà inferiore; se il bersaglio è più grande, lo restringe alla metà superiore. Questo processo si ripete finché non viene trovato l'elemento o la dimensione del sottoarray non scende a zero.
Per implementare la ricerca binaria in Python, utilizziamo due puntatori (basso e alto) per tracciare i limiti della ricerca attiva. Poiché lo spazio di ricerca diminuisce della metà ad ogni passaggio, l'algoritmo viene eseguito in tempo O(log n), rendendolo ideale per database di grandi dimensioni.
Codice e output di esecuzione
Un'implementazione di ricerca binaria iterativa standard che restituisce l'indice di un elemento di destinazione in un elenco ordinato.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
print(f"Target found at index: {index}")
else:
print("Target not found in dataset")Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5Implementazione passo dopo passo
- Indicizzazione e ricerca nelle tabelle del database
- Trovare valori di soglia o limite in intervalli matematici continui
- Funzioni di completamento automatico e ricerca nei campi di testo
Domande frequenti
L'elenco deve essere ordinato affinché la ricerca binaria funzioni?
Sì, la ricerca binaria si basa strettamente sull'ordinamento degli elementi. Se l'elenco non è ordinato, la logica di confronto si interrompe ed è necessario prima ordinare l'elenco o utilizzare una ricerca lineare.
Perché utilizzare la ricerca binaria iterativa rispetto alla ricerca binaria ricorsiva?
Sebbene la ricerca binaria ricorsiva sia elegante, la ricerca binaria iterativa è spesso preferita nella produzione. L'approccio iterativo viene eseguito nello spazio ausiliario O(1), mentre la ricerca ricorsiva occupa lo spazio O(log n) a causa dello stack di chiamate, rischiando l'overflow dello stack su input estremamente grandi.
Argomenti correlati
Esplora gli algoritmi di ordinamento di Python. Visualizza l'ordinamento a bolle e unisci l'ordinamento in modo nativo all'interno del contesto IDE del browser.
Tutorial sull'algoritmo di ordinamento di unione PythonScopri come implementare Merge Sort in Python. Un esempio interattivo passo dopo passo della strategia di ordinamento Divide and Conquer.
Guida all'algoritmo Python QuicksortEsplora l'algoritmo Quicksort in Python. Scopri la selezione del pivot, il partizionamento e la ricorsione in questo esempio di codice interattivo.