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.

Exemple de căutare binară recursivă modificare

//C++
#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=0;i<n;i++)  //Vectorul incepe de pe pozitia 0 pana la n-1
        cin>>v[i];
    cout<<"elementul "<<x<<" a fost gasit pe pozitia: "<<caut (0,n-1);
    return 0;
}
//C#
using System;

namespace Wikipedia
{
    class CautareBinaraRecursiva
    {
        static int n, x, m;
        static int[] v;
        static void Main(string[] args)
        {
            n = 0;
            x = 0;
            m = 0;
            
            Console.Write("n= "); // Citim n
            n = int.Parse(Console.ReadLine());

            v = new int[n]; // Definim vectorul

            Console.Write("x= "); // Citim x
            x = int.Parse(Console.ReadLine());

            Console.WriteLine("Introduceti elemente in ordine crescatoare: ");

            for (int i = 0; i < n; i++)
                v[i] = int.Parse(Console.ReadLine()); // Stocam valorile introduse

            Console.WriteLine("Elementul a fost gasit pe pozitia {0}!", caut(0, n - 1));
            Console.ReadKey();
        }

        static int caut(int s, int d)
        {
            if (s > d)
                return -1;

            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);
        }
    }
}

Legături externe modificare