Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Cautare binara

c



+ Font mai mare | - Font mai mic



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

b,m =

1,m, daca x=a(m), mI

0,m, daca a(m-1) < x < a(m), mI, a(0)=-

a(n+1)=+

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 G1n in modul urmator:

initial p:=1, q:=n;

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

Observatia 5.1

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

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



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

Exemplul 5.1

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

Arborele binar G1n 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 2k-1 ≤ n < 2k 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 2k ≤ n < 2k+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 2k-1 ≤ n < 2k 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 2k-1 ≤ n < 2k 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.





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1188
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved