2 Cautarea binara
Cautarea binara este cea mai simpla
aplicatie a metodei divide et impera, fiind cunoscuta inca inainte de aparitia
calculatoarelor. In esenta, este algoritmul dupa care se cauta un cuvint intr-un
dictionar, sau un nume in cartea de telefon.
Fie T[1 .. n] un tablou ordonat crescator si x
un element oarecare. Problema consta in a-l gasi pe x in T, iar
daca nu se afla acolo in a gasi pozitia unde poate fi inserat. Cautam deci indicele
i astfel incat 1 i n
si T[i] x < T[i+1],
cu conventia T[0] = -, T[n+1] = +.
Cea mai evidenta metoda este cautarea secventiala:
function sequential(T[1 .. n], x)
{cauta secvential pe x in tabloul T }
for i 1 to n do
if T[i] > x then return i-1
return
n
Algoritmul necesita un timp in Q(1+r),
unde r este indicele returnat; aceasta inseamna Q(1)
pentru cazul cel mai favorabil si Q(n) pentru
cazul cel mai nefavorabil. Daca presupunem ca elementele lui T sunt distincte,
ca x este un element al lui T si ca se afla cu probabilitate egala
in oricare pozitie din T, atunci bucla for se executa in medie
de (n2+3n-2)/2n
ori. Timpul este deci in Q(n) si pentru cazul
mediu.
Pentru a mari viteza de cautare, metoda
divide et impera sugereaza sa-l cautam pe x fie in prima jumatate a lui T,
fie in cea de-a doua. Comparandu-l pe x cu elementul din mijlocul tabloului, putem decide in care dintre
jumatati sa cautam. Repetand recursiv procedeul, obtinem urmatorul algoritm de cautare binara:
function binsearch(T[1 .. n], x)
{cauta binar pe x in tabloul T}
if
n = 0 or x < T[1] then return 0
return
binrec(T[1 .. n], x)
function binrec(T[i .. j], x)
{cauta binar pe x in subtabloul T[i .. j]; aceasta procedura
este apelata doar cand T[i]
x < T[ j+1] si i
j}
if
i = j then return i
k
(i+j+1) div 2
if
x < T[k] then return binrec(T[i .. k-1], x)
else return
binrec(T[k .. j], x)
Algoritmul binsearch necesita un timp in Q(log n),
indiferent de pozitia lui x in T (demonstrati acest lucru, revazand
Sectiunea 5.3.5). Procedura binrec executa doar un singur apel recursiv,
in functie de rezultatul testului x < T[k].
Din aceasta cauza, cautarea binara este, mai curand, un exemplu de simplificare,
decat de aplicare a tehnicii divide et impera.
Iata si versiunea iterativa a acestui
algoritm:
function iterbin1(T[1 .. n], x)
{cautare binara iterativa}
if
n = 0 or x < T[1] then return 0
i
1; j n
while
i < j do
{T[i] x < T[ j+1]}
k (i+j+1) div 2
if x < T[k] then j
k-1
else i
k
return
i
Acest algoritm de cautare binara pare
ineficient in urmatoarea situatie: daca la un anumit pas avem x = T[k], se continua totusi
cautarea. Urmatorul algoritm evita acest inconvenient, oprindu-se imediat
ce gaseste elementul cautat.
function iterbin2(T[1 .. n], x)
{varianta a cautarii binare
iterative}
if n = 0 or x < T[1] then return 0
i
1; j n
while
i < j do
{T[i] x < T[ j+1]}
k (i+j) div 2
case x < T[k]: j
k-1
x T[k+1]: i k+1
otherwise: i, j k
return
i
Timpul pentru iterbin1 este in Q(log n).
Algoritmul iterbin2 necesita un timp care depinde de pozitia lui x
in T, fiind in Q(1), Q(log n),
Q(log n) pentru cazurile cel mai favorabil,
mediu si respectiv, cel mai nefavorabil.
Care din acesti doi algoritmi este oare mai
eficient? Pentru cazul cel mai favorabil, iterbin2
este, evident, mai bun. Pentru cazul cel mai nefavorabil, ordinul timpului este
acelasi, numarul de executari ale buclei while
este acelasi, dar durata unei bucle while
pentru iterbin2 este ceva mai mare;
deci iterbin1 este preferabil, avand
constanta multiplicativa mai mica. Pentru cazul mediu, compararea celor doi
algoritmi este mai dificila: ordinul timpului este acelasi, o bucla while in iterbin1 dureaza in medie mai putin decat in iterbin2, in schimb iterbin1
executa in medie mai multe bucle while
decat iterbin2.
