[Algoritmi] Complessità Ricerca Binaria

[stefano86]

Ciao a tutti, sto studiando la ricerca binaria ma non capisco come si arriva a determinare la complessità dell'algoritmo, ovvero il numero dei passi necessari per restituire il risultato.

L'algoritmo è questo (Java):

Codice:

public static int ricercaBin(int x, int[] a) {
   int inf = 0;
   int sup = a.length - 1;
   while(inf <= sup) {
      int i = (inf + sup)/2;
      if(x < a[i])
         sup = i - 1;
      else if(x > a[i])
         inf = i + 1;
      else
         return i;
   }
   return -1; //x non in a: valore impossibile di indice
}

So che il numero di iterazioni è dato dal numero di volte che possiamo dimezzare il vettore, cioè:
$n -> n/2 -> (n/2)/2=n/2*1/2=n/2^2 → (n/2^2 )/2=n/2^2 *1/2=n/2^3 -> ...$

Ovvero:
$n → n/2^1 → n/2^2 → n/2^3 → ⋯ → n/2^i → ⋯$

Con $i$ = numero di passi e $n$ = lunghezza dell’array.

Ora si afferma che il numero di iterazioni del ciclo è, nel caso peggiore, circa $log_2 n$. Perchè?

Come si arriva a $log_2 n$ da $n → n/2^1 → n/2^2 → n/2^3 → ⋯ → n/2^i → ⋯$?

So che il logaritmo si definisce in questo modo: $x=a^y harr y=log_a x$.

Ma non mi sono chiari i passaggi usati per arrivare a $log_2 n$. Qualcuno saprebbe gentilmente spiegarmeli?

Grazie mille

[probid]

Ora devi chiederti quale sia il caso pessimo e raggiungendo quale lunghezza del sottoarray si verifichi.
Quanto vale $i$ in corrispondenza?

Ciao!

[stefano86]

Il caso pessimo è quando l'elemento da cercare non esiste nell'array scelto.. mhhh

[good91]

Generalmente alla $ i-esima $ iterazione la distanza è pari a $ n/2^(i-1) $.
Il ciclo quindi si arresta al passo $ i $ successivo a quello in cui $ n/2^(i-1)=1 $
Quindi $ i=
log_2 n +1 $. Visto che ad ogni passo si effettua solo un confronto, il numero massimo di confronti è:
$
log_2 n +1 $ $ ~$ $ log_2 n $

[stefano86]

Generalmente alla $ i-esima $ iterazione la distanza è pari a $ n/2^(i-1) $.
Il ciclo quindi si arresta al passo $ i $ successivo a quello in cui $ n/2^(i-1)=1 $
Quindi $ i=
log_2 n +1 $. Visto che ad ogni passo si effettua solo un confronto, il numero massimo di confronti è:
$
log_2 n +1 $ $ ~$ $ log_2 n $

Ciao, grazie mille per la risposta.. Cosa intendi con distanza?

[stefano86]

Scusate ma non ho ancora capito.. So che è una cosa stupida ma non ci arrivo