Tipuri De Cautari In C++

[+skyler_sdf]

1. Cautarea secventiala in tabloul ordonat

Fie v sortat crescator v1<=v2<=...<=vn

La compararea unui element vi u k avem urmatoarele 3 situatii:

1. vi=k, algoritmul se incheie, cautarea cu succes

2. vi>k, algoritmul se incheie, cautare fara succes

3. vi<k, se continua cautarea daca i<=n

#include<iostream.h>

#include<conio.h>

int v[20], n, i, k, gata, gasit, int, aux;

void sortare()

{

do{

ind=0;

for(i=1; i<=n-1; i++)

{

if(v[i]>v[i+1])

{

aux=v[i];

v[i]=v[i+1];

v[i+1]=aux;

ind=1;

}

}

}

while(ind!=0);

}

void afisare()

{

for(i=1; i<=n; i++)

cout<<v[i]<<" ";

}

void main()

{

cout<<"dati nr de elemente ale vectorului: ";

cin>>n;

for(i=1; i<=n; i++)

{

cout<<"v["<<i<<"]="; cin>>v[i];

}

sortare();

cout<<"vectorul sortat este: ";

afisare();

cout<<endl<<"dati valoarea pe care o caut: ";

cin>>k;

gata=0;

gasit=0;

i=1;

while(i<=n && !gata)

{

if(v[i]==k)

{

gata=1;

gasit=1;

}

else

if(v[i]>k)

gata=1;

else

i++;

}

if(i>n || !gasit)

cout<<"valoarea data nu se alfa in vector";

else

cout<<"valoarea data se afla in vector";

getch();

}

2.Cautarea binara(caz in care tabloul este ordonat)-var. recursiva

#include<iostream.h>

#include<conio.h>

int v[20], n, k, c;

void citire()

{

int i;

cout<<"Elementele sirului in ordine crescatoare: ";

cout<<"v[i]="; cin>>v[1];

for(i=2; i<=n; i++)

do{

cout<<"v["<<i<<"]="; cin>>v[i];

}while(v[i]<=v[i-1];

}

void afisare()

{

int i;

for(i=1; i<=n; i++)

cout<<v[i]<<" ";

}

int cautare(int k, int inf, int sup)

{

int mij; //mijlocul

//inf=capatul de inceput

//sup=sfarsitul

if(inf<=sup)

{

mij=(inf+sup)/2;

if(v[mij]==k)

return mij; //a gasit valoarea data pe pozitia mij

else

if(v[mij]>k)

cautare(k, inf, mij-1); //cauta in partea din stanga

else

cautare(k, mij+1, sup); //cauta in partea din dreapta

}

else

return 0;

}

void main()

{

do{

cout<<"dati nr de elemente ale vectorului: ";

cin>>n;

}while(n<1 || n>20);

citire();

cout<<"vectorul dat: ";

afisare();

cout<<endl<<"dati valoarea pe care o caut: ";

cin>>k;

c=cautare(k, 1, n);

if(c==0)

cout<<"valoarea data nu se afla in sir";

else

cout<<"valoarea se gaseste in sir";

getch();

3.Cautarea secventiala- nu se specifica nimic despre elementele vectorului v

#include<iostream.h>

#include<conio.h>

void main()

{

int v[20], n, i, k;

cout<<"dati nr de elementle ale vectorului: ";

cin>>n;

for(i=1; i<=n; i++)

{

cout<<"v["<<i<<"]="; cin>>v[i];

}

cout<<endl<<"dati valoarea pe care o caut: ";

cin>>k;

i=1;

while(i<=n && v[i]!=k)

i++;

if(i<=n)

cout<<"valoarea se afla in sir";

else

cout<<"valoarea nu se gaseste in sir";

getch();

}