Algoritmi: Căutarea Binară

Căutarea binară (Binary Search) este un algoritm care caută poziţia unei valori într-o colecţie de date, sau vector, sortată. La fiecare pas, algoritmul compară valoarea căutată cu valoarea din mijlocul vectorului. Dacă se potrivesc atunci indicele sau poziţia valorii în vector este returnată. În caz contrar se caută în subvectorul din stânga valorii din mijloc, dacă valoarea căutată este mai mică decât cea din mijloc, sau în subvectorul din dreapta, dacă este mai mare. Algoritmul repetă aceiaşi paşi pentru fiecare subvector. Dacă nu se găseşte valoarea se va returna valoarea -1.
Complexitatea algoritmului este \(O(\log{n})\) (logaritmic) deoarece la fiecare pas vectorul este înjumătăţit.

Implementare în C++

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}

Exemplu:

#include <iostream>
using namespace std;

// *** Binary Search *** //
// d (dreapta) - limita inferioara 
// s (stanga) - limita superioara
int cauta(int d, int s, int key, int * v)
{
    if(s < d) return -1; // Nu s-a gasit nicio valoare
    int m = (d + s) / 2; // Elementul din mijloc
    if(key < v[m]) return cauta(d, m-1, key, v); // Cauta in subvectorul din stanga
    else if(key > v[m]) return cauta(m+1, s, key, v); // Cauta in subvectorul din dreapta
    else return m; // Gasit!
}

int main()
{
    int iteme[] = {2, 9, 11, 15, 28, 33, 40, 47, 51, 64, 76, 77, 82, 85, 94}; // 15 elemente
    int indice = cauta(0, 14, 76, iteme);
    cout << indice; // 10; iteme[10] == 76;
    
    system("PAUSE");
    return 0;
}