Ricerca binaria

La ricerca binaria si applica agli array ordinati.

Essa controlla se l’elemento richiesto si trova nella posizione centrale dell’array altrimenti concentra la ricerca nella parte

• BASSA se ha trovato un elemento MAGGIORE
• ALTA se ha trovato un elemento MINORE

e continua finché

• non trova l’elemento,
• oppure rimane da esaminare un sottoarray vuoto.

Esempio

Sia V = (10, 25, 30, 40, 41, 42, 60)

Nel caso ottimo, l’elemento richiesto occupa la posizione centrale e basta un unico passo
Nel caso pessimo, sono necessari 3 passi
Se l’elemento non è presente si scopre dopo i 3 passi del caso pessimo.

Function Binaria(V: Vettore; N: Integer; K: Real): Integer;
Var
   INF   ,
   SUP   ,
   MEDIO : Integer;
   ANCORA: Boolean;
Begin
   INF:=1;
   SUP:=N;
   ANCORA:=True;
   While(INF <= SUP) And (ANCORA) Do
      Begin
         MEDIO:=(INF+SUP) Div 2;
         If(V[MEDIO] < K) Then
            INF:=MEDIO+1
         Else If(V[MEDIO] = K) Then
            ANCORA:=False
         Else
            SUP:=MEDIO-1;
      End;
   If(ANCORA) Then
      Binaria:=0
   Else
      Binaria:=MEDIO;
End;

Semplifico

Function Binaria(V: Vettore; N: Integer; K: Real): Integer;
Var
   INF  ,
   SUP  ,
   MEDIO: Integer;
   RISP : Integer; 
Begin
   INF:=1;
   SUP:=N;
   RISP:=0;
   While(INF <= SUP) And (RISP = 0) Do
      Begin
         MEDIO:=(INF+SUP) Div 2;
         If(V[MEDIO] < K) Then
            INF:=MEDIO+1
         Else if(V[MEDIO] = K) Then
            RISP:=MEDIO
         Else
            SUP:=MEDIO-1;
      End;
   Binaria:=RISP; 
End;

---

Analizziamo il codice

Function ricercaBinaria(V: Vettore; N: Integer; K: Real): Integer;
Var
   INF  ,
   SUP  ,
   MEDIO,
   RISP : Integer;
Begin
   INF :=1;
   SUP :=N;
   RISP:=0;
   While(INF <= SUP) And (RISP = 0) do
      Begin
         MEDIO:=(INF+SUP) Div 2;
         If(V[MEDIO] < K) Then
            INF:=MEDIO+1
         Else if(V[MEDIO] = K) Then
            RISP:=MEDIO
         Else
            SUP:=MEDIO-1;
      End;
   ricercaBinaria:=RISP;
End;

Utilizzando la tecnica di calcolo della complessità in tempo possiamo concludere che

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): c₁+c₂*1
• elemento trovato al 2° passo: c₁+c₂*2
• ...
• elemento trovato all'ultimo passo: c₁+c₂*(m-1)
• elemento non presente: c₁+c₂*m

Supponiamo pessimisticamente di dover aspettare sempre fino all'ultimo passo, allora

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

quindi, nel caso pessimo

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!