[C++]Cautare binara

[~Wolf~]

Algoritm pentru cautarea binara

"Se da un sir de numere ordonat crescator cu N elemente, se cere sa se returneze pozitia in sir a unui numar introdus de la tastatura."

Cum lucreaza algoritmul?

Vom avea 3 variabile:
Stanga : inceputul intervalului in care cautam
Mijloc : mijlocul intervalului
Dreapta : sfarsitul intervalului in care cautam

Le voi prescurta St,Dr,Mij in program.Practic cele 3 sunt prima pozitie, pozitia mijlocie si ultima pozitie din vector.

Algoritmul verifica de repetate ori daca mijlocul este egal cu numarul cautat, returnand pozitia sa, insa intervalul se modifica odata cu parcurgerea.Astfel vom impune 3 conditii, cat timp St<=Dr:
if(Mij==nr) -in cazul acesta, daca conditia este adevarata elementul a fost gasit
if(nr<v[Mij]) -daca nr este mai mic decat v[Mij], Dr va deveni Mij
if(nr>v[Mij]) -daca nr este mai mare decat v[Mij], St va deveni Mij


#include <iostream>
using namespace std;
int n,numar,i,v[101];
int Cautare_Binara(int St, int Dr) //construim o functie cu 2 parametri, stanga si dreapta
{
while(St<=Dr)
{
int Mij=(St+Dr)/2; //declaram mijlocul si ii dam valoare
if(numar==v[Mij]) //daca numarul este egal cu mijlocul, am gasit solutia si am returnat-o
return Mij;
if(numar>v[Mij]) //daca numarul este mai mare decat elementul din mijloc, ne mutam spre "partea din dreapta"
St=Mij+1;
if(numar<v[Mij]) //daca numarul este mai mic decat elementul din mijloc, ne mutam spre "partea din stanga"
Dr=Mij-1;
}
}
int main()
{
cout<<"Introduceti numarul elementelor: ";
cin>>n;
cout<<endl<<"Introduceti elementele in ordine crescatoare: ";
for(i=0;i<n;i++)
cin>>v;
cout<<endl<<"Introduceti numarul pe care vreti sa-l cautati: ";
cin>>numar;
cout<<endl<<"Elementul accesat se afla pe pozitia: "<<Cautare_Binara(0,n); //apelam functia cu prima pozitie care e 0, si ultima care e n
return 0;
}


[I]Exemplu:


10 //numarul elementelor
12 23 45 47 56 59 62 78 90 99 // elementele
47 //numarul pe care il vom cauta


Algoritmul va lucra in felul urmator: va citi numerele, apoi cand ajunge la apelarea functiei intram in ea.


Pasul 1:
Ne intrebam daca St<=Dr => Adevarat, 0<=10
Mij=(0+10)/2=5
-numarul 47 este mai mic decat 59(care este pe pozitia mijlocie, 5)
Dr=Mij-1 => Dr=4

Pasul 2:
Ne intrebam daca St<=Dr => Adevarat, 0<=4
Mij=(0+4)/2=2
-numarul 47 este mai mare decat 45(care este pe pozitia mijlocie, 2)
St=Mij+1 => St=3

Pasul 3:
Ne intrebam daca St<=Dr => Adevarat, 3<=4
Mij=(3+4)/2=3
-numarul 47 este egal cu Mij => returnam Mij => returnam 3

Se va afisa 3