Ricerca binaria

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Ricerca binaria

L'algoritmo di ricerca binaria

function Ricerca(V: Vettore; N: Integer; K: Elemento): 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
      Ricerca:=0
   else
      Ricerca:=MEDIO;
end;

Possiamo concludere, come prima, che

T(x) = c₁+c₂x

e trascurare i conteggi.

I calcoli per T danno

	Vettore vuoto: ...
	Trovato alla posizione di mezzo (al primo passo): c₁+c₂
	...

	Trovato all'ultimo passo: ...
	Non presente: c₁+c₂m

Quanto vale m? La dimensione del vettore sul quale si effettua la ricerca volta per volta è

N(N-1)/2 ~ N/2¹((N/2)-1)/2 ~ N/4 = N/2²... = N/8 = N/2³…
... = N/N = 1

Quando la potenza di 2 a denominatore raggiunge N il ciclo while() termina sicuramente, cioè quando

2^m = N

quindi nel caso pessimo

T = c₁+c₂m = c₁+c₂log₂N

Esempi numerici

N	m
2⁴= 16 ~ 10¹	4
2⁸= 256	8
2¹⁰= 1.024 ~ 10³	10
2¹⁶= 65.536	16
2²⁰= 1.048.576 ~ 10⁶	20
2³⁰= 1.073.741.824 ~ 10⁹	30

Ipotizzando, pessimisticamente, che i coefficienti siano molto sfavorevoli per la ricerca binaria, per esempio

T_seq(n) = 5*n+5
T_bin(n) = 100*log₂n+100

calcoliamo i tempi di attesa al variare di n

n	T_seq(n)	T_bin(n)
16	5*16+5 = 85	100*4+100 = 500
256	5*256+5 = 1285	100*8+100 = 900
1.024	5*1.024+5 = 5125	100*10+100 = 1.100
65.536	~10⁵	100*16+100 = 1.700
1.048.576	~10⁶	100*20+100 = 2.100
1.073.741.824	~10⁹	100*30+100 = 3.100

Anche in questa situazione di svantaggio l'algoritmo di ricerca binaria si comporta meglio se applicato ad appena 200 elementi!

Ricerca binaria - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito