Ricerca binaria

di

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.

Nel caso ottimo …
l’elemento richiesto occupa la posizione centrale,
basta un unico passo.

rb1

Nel caso pessimo…
sono necessari 3 passi.

rb2

Se l’elemento non è presente…
si scopre dopo i 3 passi del caso pessimo.

rb3p

Riepilogo posizione -> passi

Codifica

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;