Cautare binara

Cautare binara

Se dau un vector a=(a(1), , a(n)) de numere reale si un numar real x. Se cere sa se determine daca x se afla printre elementele vectorului a.

Rezolvare

Daca a este un vector oarecare atunci trebuie parcurse secvential elementele vectorului. Daca exista un element a(m) egal cu x, atunci se spune ca se efectueaza o cautare cu succes. Daca insa nici unul dintre elementele vectorului a nu este egal cu x se spune ca se efectueaza o cautare fara succes. Daca se parcurg secvential elementele vectorului a atunci sunt necesare cel mult n comparatii in cazul unei cautari cu succes si exact n comparatii in cazul unei cautari fara succes. Numarul mediu de comparatii in cazul unei cautari cu succes este (1++n)/n= n(n+1)/2n= (n+1)/2.

In continuare se presupune ca a(1)≤ ≤a(n). Daca nu este indeplinita aceasta conditie atunci se sorteaza mai intai cele n elemente ale vectorului a.

Pentru rezolvarea problemei de cautare binara se utilizeaza metoda divide et impera. Algoritmul de rezolvare este prezentat sub forma unei proceduri numita CAUTBIN.

PROCEDURA CAUTBIN(A, N, X)

BEGIN

ARRAY A(N);

P:=1; Q:=N; B:=0;

WHILE P≤Q DO

BEGIN

M:= (P+Q)/2

IF X=A(M)

THEN B:=1

ELSE IF X>A(M)

THEN P:=M+1

ELSE Q:=M-1;

END;

IF B=1 THEN WRITE B,N

ELSE WRITE B,P;

END;

Programul C corespunzator este urmatorul:

#include<stdio.h>

int cautbin(int a[20], int n, int x)

return 0;

void main()

printf('Elementul cautat: ');

scanf('%d',&x);

//se afiseaza pozitia pe care se gaseste elem in sir

//sau 0 daca elem nu se gaseste in sir

printf('Se gaseste pe pozitia: %dn',cautbin(a,n,x));

In procedura CAUTBIN solutia se exprima sub forma

Intr-adevar, daca se executa o cautare cu succes atunci b=1 si se tiparesc b,m. Daca se executa o cautare fara succes atunci b=0 si se tiparesc b,p, unde p=m daca a(m-1)<x<a(m). Pentru a dovedi aceasta afirmatie precizam ca la ultima iteratie a instructiunii WHILE ne aflam in situatia p=q=m. Daca x<a(m) atunci p=m, q=m-1 si deoarece p>q se iese din instructiunea WHILE, deci x< a(m+1) = a(p).

Algoritmului de cautare binara aplicat vectorului a=(a(1), , a(n)) i se poate asocia un arbore binar G_1n in modul urmator:

initial p:=1, q:=n;

unei subsecvente (a(p), , a(q)) din vectorul a i se asociaza subarborele G_pq care are forma din figura 5.1, unde m:= (p+q)/2

Observatia 5.1

Pentru p=q=t se obtine subsecventa (a_t) si i se asociaza subarborele G_tt care este nodul terminal t. Orice nod terminal al arborelui binar se obtine sub aceasta forma.

Parcurgerea in inordine a arborelui binar G_1n este 1, , n.

Numele de cautare binara se datoreste tocmai acestui arbore binar G_1n.

Exemplul 5.1

Sa consideram cazul n=5. Se obtine arborele binar din figura 5.2.

Arborele binar G_1n se transforma intr-un arbore binar complet prin adaugarea a n+1 noduri fictive la cele n noduri efective in modul urmator: fiecarui nod efectiv m care are cel mult un succesor i se adauga succesori fictivi astfel:

• daca nodul efectiv m nu are succesor stang atunci i se adauga succesorul fictiv m';
• daca nodul efectiv m nu are succesor drept atunci i se adauga succesorul fictiv (m+1)'.

In arborele binar complet , construit ca mai sus, nodurile efective m, m=1, , n, sunt noduri interne si nodurile m', m'=1', , (n+1)' sunt noduri terminale. Parcurgerea in inordine a arborelui binar complet este 1', 1, 2', 2, , n', n, (n+1)'. Se observa ca nodul terminal m' corespunde intervalului (a(m-1), a(m)).

Pentru exemplul prezentat in figura 5.2 obtinem arborele binar complet prezentat in figura 5.3.

Conform algoritmului de cautare binara rezulta urmatoarele:

• daca x<a(m) atunci se continua pe subarborele stang al subarborelui cu radacina m din arborele binar complet
• daca x>a(m) atunci se continua pe subarborele drept al subarborelui cu radacina m din arborele binar complet
• o cautare cu succes va conduce la unul din nodurile interne m din arborele binar complet
• o cautare fara succes va conduce la unul din nodurile terminale m' din arborele binar complet
• numarul de comparatii in fiecare caz este egal cu numarul de noduri interne care se gasesc pe drumul care uneste nodul radacina cu nodul care reprezinta sfarsitul procesului de cautare.

Exemplul 5.2

Sa consideram cazurile x=a(4) si a(4) < x < a(5); daca x=a(4) atunci drumul de cautare binara este D=(3,4) si deci se fac doua comparatii; daca a(4) < x < a(5) atunci drumul de cautare binara este D=(3, 4, 5, 5') si deci se fac 3 comparatii.

Teorema 5.1

Algoritmul de cautare binara are complexitatea O(log n).

Demonstratie

Daca n verifica inegalitatile 2^k-1 ≤ n < 2^k atunci prin inductie dupa k aratam ca nodurile terminale 1', , (n+1)' ale arborelui binar complet se afla pe nivelurile k-1 si k. Nodul radacina se afla pe nivelul 0. Pentru k=1 rezulta n=1 si arborele binar complet corespunzator este reprezentat in figura 5.4. Deoarece nodurile terminale 1', 2' se afla pe nivelul 1 rezulta ca pentru k=1 afirmatia este adevarata.

Presupunem afirmatia adevarata pentru k si sa demonstram pentru k+1. Fie 2^k ≤ n < 2^k+1 si arborele binar complet cu nodul radacina m = (n+1)/2 , _1m-1 subarborele stang si subarborele drept. Conform ipotezei inductiei subarborii si au nodurile terminale pe nivelurile k-1 si k. Rezulta ca pentru arborele binar complet nodurile terminale se afla pe nivelurile k si k+1. Deci, daca 2^k-1 ≤ n < 2^k atunci nodurile terminale ale arborelui binar complet se afla pe nivelurile k-1 si k. Deoarece numarul de comparatii este egal cu numarul de noduri interne care se gasesc pe drumul de la nodul radacina la nodul care reprezinta sfarsitul procesului de cautare, rezulta ca:

o cautare cu succes necesita cel mult k comparatii;

o cautare fara succes necesita k-1 sau k comparatii.

Din inegalitatile 2^k-1 ≤ n < 2^k rezulta k= log n +1. Deci complexitatea algoritmului de cautare binara este O(log n).

Exemplul 5.3

Sa consideram n=1000. Daca elementele vectorului a nu sunt sortate atunci trebuie efectuate in medie 500 de comparatii in cazul unei cautari cu succes si 1000 de comparatii in cazul unei cautari fara succes. Daca elementele sunt sortate si utilizam algoritmul de cautare binara atunci trebuie efectuate cel mult k = log 1000 +1 = 10 comparatii in cazul unei cautari cu succes si 9 sau 10 comparatii in cazul unei cautari fara succes.