Rilasciato · in miglioramento
Algorithm
Gli algoritmi di ricerca trovano valori o posizioni: ricerca lineare e binaria, lower_bound e upper_bound, ricerca sulla risposta e tabelle hash.
Cercare significa trovare un valore in una raccolta di dati, oppure la posizione in cui una condizione diventa vera per la prima volta. La ricerca lineare controlla gli elementi uno alla volta e funziona con qualsiasi dato, mentre la ricerca binaria dimezza a ogni passo un intervallo ordinato e con un milione di elementi richiede solo una ventina di confronti. Per le corrispondenze esatte, una tabella hash risponde in tempo costante in media.
La ricerca è fondamentale perché quasi ogni programma consulta dati: indici di database, completamento automatico, analisi dei log e tabelle di routing si basano su di essa. La ricerca binaria, inoltre, non si limita agli array. Quando una condizione sì/no cambia una sola volta lungo un intervallo, si può cercare in modo binario la risposta stessa, e molti problemi di ottimizzazione dei colloqui tecnici diventano codice breve e affidabile.
Conviene iniziare scrivendo da sé una ricerca lineare e una ricerca binaria su intervallo chiuso, poi esercitarsi con le forme lower_bound e upper_bound su intervallo semiaperto finché la gestione dei bordi non diventa naturale. Simulate a mano piccoli array, confrontate il vostro codice con il modulo bisect di Python usando input casuali e infine affrontate la ricerca sulla risposta e la ricerca ternaria con problemi di ottimizzazione.
Confronta gli elementi uno alla volta in tempo O(n). Non richiede ordinamento ed è spesso la scelta più veloce per raccolte piccole.
Dimezza a ogni passo un intervallo ordinato e trova i valori in tempo O(log n). La versione iterativa usa solo O(1) di memoria aggiuntiva.
Restituiscono la prima posizione con valore maggiore o uguale, o strettamente maggiore, al valore cercato. La loro differenza conta i duplicati, e il modulo bisect di Python le offre entrambe.
La ricerca parametrica trasforma la domanda sul più piccolo valore ammissibile in un test sì/no e cerca in modo binario nell'intervallo delle risposte possibili.
lower_bound restituisce il primo indice con valore maggiore o uguale a x, lavorando sull'intervallo semiaperto [lo, hi). Se il valore centrale è minore di x scarta la metà sinistra, altrimenti quella destra. contains usa quell'indice per verificare se il valore è presente, e l'ultima riga conferma che il risultato coincide con bisect.bisect_left della libreria standard.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Ricerca.
Fai domande, condividi la tua esperienza e scambia opinioni su Ricerca.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.