[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):

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² → (n/2² )/2=n/2² *1/2=n/2³ -> ...


Ovvero:
n → n/2¹ → n/2² → n/2³ → ⋯ → n/2_ⁱ → ⋯


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₂n. Perchè?


Come si arriva a log₂n da n → n/2¹ → n/2² → n/2³ → ⋯ → n/2ⁱ → ⋯?


So che il logaritmo si definisce in questo modo: x=a^y → y=log_ax.


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


Grazie mille :-)

[MItaly]

L'algoritmo si ferma quando arrivi a considerare un intervallo lungo 1, ovvero quando sei a
n/2ⁱ = 1
n = 2ⁱ
log₂(n) = log₂(2ⁱ)
log₂(n) = i

[stefano86]

Grazie infinite! Finalmente ho capito. Grazie

[MItaly]