Analizziamo il codice
int ricercaBinaria(double v[], double k)
{
int risp=-1,
inf=0,
sup=v.length-1,
medio;
while(inf <= sup && risp == -1)
{
medio=(inf+sup)/2;
if(v[medio] < k)
inf=medio+1;
else if(v[medio] == k)
risp=medio;
else
sup=medio-1;
}
return risp;
}
Utilizzando la tecnica di calcolo della complessità in tempo possiamo concludere che
T(x) = c1+c2x
con x il numero di volte che viene eseguito il ciclo.
I calcoli approssimati per T danno
- vettore vuoto: ~7
- elemento trovato al 1° passo (in mezzo): c1+c2*1
- elemento trovato al 2° passo: c1+c2*2
- ...
- elemento trovato all'ultimo passo: c1+c2*(m-1)
- elemento non presente: c1+c2*m
Supponiamo pessimisticamente di dover aspettare sempre fino all'ultimo passo, allora
T(n)=c1+c2*m.
Quanto vale m?
La dimensione del vettore sul quale si effettua la ricerca passo-passo è
- n
- ~n/2
- ~n/4
- ~n/8
- ...
- 2
- 1
- 0 ...
Quando il valore della potenza di 2 a denominatore raggiunge n il ciclo termina sicuramente, cioè per
2m = n
quindi, nel caso pessimo
T(n) = c1+c2m = c1+c2log2n
Esempi numerici
| n | m | |
| 24 | 16 | 4 |
| 28 | 256 | 8 |
| 210 | 1.024 | 10 |
| 216 | 65.536 | 16 |
| 220 | 1.048.576 | 20 |
| 230 | 1.073.741.824 | 30 |
L’algoritmo di ricerca binaria applicato a un vettore con un miliardo di elementi garantisce una risposta dopo appena 30 passi!