DAA - Ricerca binaria

In questo capitolo, discuteremo un altro algoritmo basato sul metodo divide et impera.

Dichiarazione problema

La ricerca binaria può essere eseguita su un array ordinato. In questo approccio, l'indice di un elementoxviene determinato se l'elemento appartiene all'elenco degli elementi. Se l'array non è ordinato, viene utilizzata la ricerca lineare per determinare la posizione.

Soluzione

In questo algoritmo, vogliamo trovare se element x appartiene a un insieme di numeri memorizzati in un array numbers[]. Dovel e r rappresentano gli indici sinistro e destro di un sotto-array in cui deve essere eseguita l'operazione di ricerca.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

Analisi

La ricerca lineare viene eseguita O(n)tempo. Mentre la ricerca binaria produce il risultato inO(log n) tempo

Permettere T(n) essere il numero di confronti nel caso peggiore in un array di n elementi.

Quindi,

$$ T (n) = \ begin {cases} 0 & if \: n = 1 \\ T (\ frac {n} {2}) + 1 & altrimenti \ end {cases} $$

Utilizzando questa relazione di ricorrenza $ T (n) = log \: n $.

Pertanto, la ricerca binaria utilizza $ O (log \: n) $ time.

Esempio

In questo esempio, cercheremo l'elemento 63.