Welcome to BitCell. Click here to register !
Sa presupunem ca avem vectorul V cu n componente si cautam o valoare in acesta:
V (1, 3, 5, 6, 70, 71, 100, 101, 102, 106) cu 10 componente si cautam valoarea 3.
Stim ca vectorul este ordonat crescator, ceea ce ne permite urmatoarea deductie: Daca termenul din mijloc este mai mare decat cel cautat, cautarea se restrange in partea stanga a vectorului. Daca este mai mic atunci cautarea se restrange in partea dreapta, iar daca termenul din mijloc este egal cu cel cautat... inseamna ca l-am gasit. Acesti 3 pasi se vor aplica pana valoarea din mijloc este egala cu val sau pana cand se constata ca val nu se gaseste in acel vector.
Sa vedem cum arata intr-un limbaj de programare:
- #include<fstream>
- using namespace std;
- #define InFile "BS.in"
- #define OutFile "BS.out"
- fstream f(InFile, ios::in), g(OutFile, ios::out);
- int v[100], i, n, val, x;
- int BinarySearch(int v[100], int stanga, int dreapta, int val)//parametrii sunt: v-vectorul, stanga-initial este 1, dreapta-initial este n, val-valoarea cautata
- {
- //stanga - dreapta reprezinta intervalul in care cautam valoarea.
- // initial cautam valoarea in intervalul 1-n unde n este numarul de componente al vectorului.
- int mijloc;
- mijloc=stanga+(dreapta-stanga)/2; // mijloc este mijlocul intervalului stanga dreapta pentru care vom face cele 3 verificari
- if(stanga>dreapta) //daca am ajuns ca stanga>dreapta inseamna ca nu avem solutie
- return -1;
- if(v[mijloc]==val)//daca numarul din mijlocul intervalului stanga dreapta este val am gasit solutia
- return mijloc;//si vom returna pozitia
- else//daca nici nu am gasit solutie si nici nu am constatat ca nu exista micsoram din nou intervalul de cautare
- {
- if(v[mijloc]>val)//daca valoarea din mijlocul intervalului stanga-dreapta este mai mare decat val
- return BinarySearch(v,stanga,mijloc-1,val);//atunci val este in partea stanga a intervalului stanga dreapta, prin urmare dreapta devine mijloc-1, restrangand din nou intervalul de cautare
- if(v[mijloc]<val)//daca este mai mica, atunci valoarea trebuie sa fie in jumatatea dreapta a intervalului stanga-dreapta
- return BinarySearch(v,mijloc+1,dreapta,val);//deci stanga devine mijloc+1 si cautarile au fost restranse pe noul interval
- }
- }
- int main()
- {
- f>>n>>val;//citire numar de componente vector si valoarea cautata
- for(i=1; i<=n; ++i)//citire componente vector
- f>>v[i];
- f.close();
- x=BinarySearch(v,1,n,val);//aplicam cautarea binara pe tot vectorul (intervalul 1-n)
- if(x==-1)//daca valoarea returnata de BinarySearch este -1 inseamna ca val nu se afla in v
- g<<"Valoarea nu exista in vector.\n";
- else//altfel se afla pe pozitia x
- g<<"Valoarea se gaseste in vector pe pozitia "<<x<<".\n";
- g.close();
- return 0;
- }
Algoritmul de mai sus este pentru cazul cand vectorul este sortat crescator.
Nu este recomandat sa folositi Binary Search pentru a vedea daca o valoare exista intr-un vector nesortat deoarece se consuma extrem de mult timp sortandu-l.
Probleme propuse:
1) Se citeste un vector cu n componente numere intregi,ordonate descrescator si o valoare intreaga x.Sa se decida daca x se gaseste sau nu printre componentele vectorului, iar in cazul in care se gaseste sa se specifice pozitia lui in vector.
Sper ca va este de folos. Good luck
. Îi poți crește însă calitatea (făcându-l și mai ușor de urmărit în același timp) urmărind următoarele idei: