ALGORITMI DE CAUTARE in graf - Cautare secventiala, binara

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 secventiala 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 secventiala rapida

Cautarea secventiala 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 secventiala 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();