Cautarea binara



Elementele sunt sortate crescator


#include <iostream>

using namespace std;

int main()
{
   int n, v[11];
   cin>>n;
   for(int i=1;i<=n;i++)
      cin>>v[i];
   int x;
   cout<<"ce element doriti sa cautati in vector? ";
   cin>>x;
   int st=1, dr=n;
   bool gasit=false;
   while(st<=dr && !gasit)
   {
      int mijloc=(st+dr)/2;
      if(v[mijloc]==x)
         gasit=true;
      else if(x<v[mijloc])
               dr=mijloc-1;
            else
               st=mijloc+1;
   }
   if(gasit)
      cout<<"numarul "<<x<<" a fost gasit in vector";
   else
      cout<<"numarul "<<x<<" nu a fost gasit in vector";
}

Explicatie:

- citim elementele vectorului (acestea trebuie sa fie crescatoare, altfel trebuie sortate)
- aceasta metoda de cautare se bazeaza pe divide et impera (adica sirul se va tot imparti in doua, luandu-se mijlocul si verificand daca acesta este elementul cautat)
- cu ajutorul variabilelor st si dr se va realiza aceasta impartire
- se calculeaza mijlocul si se verifica daca am gasit elementul cerut
- in caz ca nu l-am gasit, vom verifica daca acesta se afla in stanga mijlocului sau in dreapta lui
- daca elementul cautat nu se afla in vector atunci st va deveni mai mare decat dr si algoritmul nostru se va opri