Căutare binară

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată (tablou unidimensional/vector). Algoritmul funcționează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină. Dacă e mai mare decât acea valoare, algoritmul se reia, de la mijlocul listei până la sfârșit, iar dacă e mai mică, algoritmul se reia pentru elementele de la începutul listei până la mijloc. Întrucât la fiecare pas cardinalul mulțimii de elemente în care se efectuează căutarea se înjumătățește, algoritmul are complexitate logaritmică.

Se consideră un tablou unidimensional v de n elemente deja sortat și trei variabile: i=inceput, s=sfârșit și m=mijloc. Metoda verifică de mai multe ori dacă mijlocul vectorului/tabloului unidimensional este egal cu elementul căutat:

  • în cazul în care este egală, variabila m reprezintă poziția elementului în vector;
  • dacă nu se îndeplinește condiția de egalitate se trece la verificarea poziției elementului căutat în vector astfel: dacă elementul căutat este mai mic decât elementul din mijlocul vectorului, variabila "s" ia valoarea lui "m" iar dacă nu variabila i ia valoarea lui m.

Totul se repetă atât timp cât i este mai mic decât s.

Exemplu de căutare binară recursivă[modificare | modificare sursă]

#include<iostream>
using namespace std;
int n,x,v[10],m;
int caut (int s, int d)
{
    if(s>d)
        return -1;
    else
        {
            m =(s+d)/2;
            if (x==v[m])
                return m;
            if (x<v[m])
                return caut(s,m-1);
            else
                return caut(m+1,d);
        }
}
int main()
{ 
    cout<<"n,x ";
    cin>>n>>x;
    cout<<"dati "<<n<<" elemente (in ordine crescatoare).\n";
    for (int i=1;i<=n;i++)
        cin>>v[i];
    cout<<"elementul "<<x<<" a fost gasit pe pozitia: "<<caut (1,n);
    return 0;
}

Legături externe[modificare | modificare sursă]