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


Ovvero:
n → n/21 → n/22 → n/23 → ⋯ → n/2i → ⋯


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


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


Come si arriva a log2n da n → n/21 → n/22 → n/23 → ⋯ → n/2i → ⋯?


So che il logaritmo si definisce in questo modo: x=ay → y=logax.


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


Grazie mille :-)