Cautarea binara

          Algoritumul de cautare binara este unul foarte simplu dar ofera performante mai bune decit algoritmul de cautare secventiala. El functioneaza in felul urmator:

          Se compara numarul de cautat cu elementul aflat la mijlocul sirului ( element care se mai numeste si pivot ). In cazul in care cele doua elemente coincid cautarea sa incheiat cu succes. Daca numarul de cautat este mai mare decit pivotul, se continua cautarea in aceeasi maniera in subsirul delimitat de pivot si capatul sirului initial. Daca numarul de cautat este mai mic decit pivotul se continua cautarea in aceeasi maniera in subsirul delimitat de pivot si inceputul sirului initial.

          Algoritmul prezentat se incadreaza in clasa algoritmilor elaborati conform tehnicii de programare Divide et Impera, si se poate implementa atit recursiv cit si iterativ.

          Unul din dezavantajele acestui algoritm este ca sirul in care se face cautarea trebuie sa fie initial sortat.

#include<iostream.h>

void main()

{

int i, n, x, st, dr, mijl, gasit, a[50];

cout<<"dati numarul de elemente din vector"<<endl;

cout<<"n= "; cin>>n;

cout<<"dati elementul de cautat"<<endl;

cout<<"x= "; cin>>x;

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

{ cout<<"a["<<i<<"]= "; cin>>a[i]; }

st=0; dr=n-1; gasit=0;

while (st<=dr && !gasit )

  { mijl=(st+dr)/2;

     if (a[mijl]==x)

          gasit=1;

            else

            if (x<a[mijl]) dr=mijl-1;

               else st=mijl+1; }

if (st>dr) cout<<"Nu sa gasit elementul";

   else cout<<"Elementul apartine sirului";

}