Algoritmi de cautare
Cautare secventiala
Algoritmul de cautare secventiala rezolva urmatoarea problema: daca x[n] este un vector cu valori oarecare sa se decida daca o valoare oarecare a se afla printre elementele vectorului x. Cautarea se numeste secvential 9; deoarece, pentru aflarea raspunsului, vectorul x este parcurs secvential incepand cu prima componenta pana cand este intalnita prima aparitie a valorii a (cautarea a avut succes) sau pana cand vectorul x a fost epuizat (cautarea nu a avut succes).
Implementare in limbajul C
# include 'stdio.h'
# include 'conio.h'
int x[20],n,i,a;
int CautSecv(int n,int x[],int a)
void main(void)
printf('nafisare vector: ');
for (i=1;i<=n;i++)
printf('%d ',x[i]);
printf('na=');
scanf('%d',&a);
if (CautSecv(n,x,a))
printf('Valoarea se afla printre elementele sirului');
else printf('Valoarea nu se afla printre elementele sirului');
getch();
Cautare secvential 9; rapida
Cautarea secvential 9; poate deveni « rapida » daca modificam putin algoritmul deja prezentat. Modificarea consta in completarea vectorului x pe componenta x[n+1] cu valoarea a pe care dorim sa o cautam in x[n]. Asa cum se poate constata in implementare de mai jos, numarul de comparatii se reduce substantial : adaugarea valorii a pe pozitia x[n+1] a permis eliminarea comparatiei i<=n care depisteaza sfarsitul sirului x.
Implementare in limbajul C
# include 'stdio.h'
# include 'conio.h'
int x[20],n,i,a;
int CautSecv(int n,int x[],int a)
void main(void)
printf('nafisare vector: ');
for (i=1;i<=n;i++)
printf('%d ',x[i]);
printf('na=');
scanf('%d',&a);
if (CautSecv(n,x,a))
printf('Valoarea se afla printre elementele sirului');
else printf('Valoarea nu se afla printre elementele sirului');
getch();
Cautare secvential 9; in tabel ordonat
In situatia in care elementele vectorului sunt ordonate cautarea se poate face mult mai eficient. Astfel, daca sirul este ordonat crescator este suficient sa cautam valoarea a in vectorul x doar cat timp a>x[i], i=1,2,.. Daca exista o valoare i astfel incat a<x[i] nu are rost sa cautam mai departe deoarece sirul fiind ordonat crescator, toate valorile x[j] cu j>i vor fi strict mai mari decat a.
Implementare in limbajul C
# include 'stdio.h'
# include 'conio.h'
int x[20],n,i,a;
int CautSecvTabOrd(int n,int x[],int a)
void main(void)
printf('nafisare vector: ');
for (i=1;i<=n;i++)
printf('%d ',x[i]);
printf('na=');
scanf('%d',&a);
if (CautSecvTabOrd(n,x,a))
printf('Valoarea se afla printre elementele sirului');
else printf('Valoarea nu se afla printre elementele sirului');
getch();
Cautare binara
efectueaza atribuirile inc=1, sf=n, gasit=0
cat timp inc<=sf si gasit = 0 executa
gaseste pozitia m=(inc+sf)/2care marcheaza mijlocul subvectorului cu elementele x[inc], x[inc+1],., x[sf]
daca x[m] este egal cu a atunci gasit=1, altfel
daca x[m]>aux atunci cautarea se continua in zona cuprinsa intre pozitia inc si m-1, in caz contrar cautarea se continua in zona cuprinsa intre m+1 si sf
Implementare in limbajul C
# include 'stdio.h'
# include 'conio.h'
int x[20],n,i,a;
int CautBin(int x[],int a)
return gasit;
void main(void)
printf('nafisare vector: ');
for (i=1;i<=n;i++)
printf('%d ',x[i]);
printf('na=');
scanf('%d',&a);
if (CautBin(x,a))
printf('Valoarea se afla printre elementele sirului');
else printf('Valoarea nu se afla printre elementele sirului');
getch();
