Căutarea binară

Atunci când vectorul este ordonat, putem căuta o valoare mult mai rapid decât parcurgând element cu element. Metoda se numește căutare binară și este una dintre cele mai importante tehnici studiate la liceu și la examenul de Bacalaureat.

Căutarea binară funcționează numai pe un vector ordonat (crescător sau descrescător). Dacă vectorul nu este ordonat, trebuie fie să îl ordonăm în prealabil, fie să folosim căutarea secvențială.

Ideea pornește de la felul în care căutăm un cuvânt în dicționar: nu îl luăm de la prima pagină, ci deschidem undeva la mijloc și, în funcție de litera găsită, continuăm doar în partea stângă sau în partea dreaptă. Căutarea binară face exact același lucru:

1. considerăm întregul vector drept interval de căutare, delimitat de un capăt stâng și unul drept;
2. calculăm poziția din mijloc, m;
3. dacă elementul din mijloc este chiar valoarea căutată, am terminat;
4. dacă valoarea căutată este mai mică decât elementul din mijloc, ea se poate afla doar în jumătatea stângă, așa că mutăm capătul drept înainte de mijloc;
5. altfel, continuăm în jumătatea dreaptă, mutând capătul stâng după mijloc;
6. repetăm până găsim valoarea sau până când intervalul devine vid.

Notăm capetele intervalului cu st (stânga) și dr (dreapta), iar mijlocul cu m. Presupunem vectorul ordonat crescător:

int n, v[1001], x;
// ...
int st = 0, dr = n - 1, poz = -1;
while (st <= dr) {
    int m = (st + dr) / 2;
    if (v[m] == x) {
        poz = m;
        break;
    } else if (x < v[m])
        dr = m - 1;
    else
        st = m + 1;
}
if (poz != -1)
    cout << "Gasit pe pozitia " << poz;
else
    cout << "Nu exista";

Folosim variabila poz pentru a reține poziția pe care am găsit valoarea, sau -1 dacă aceasta nu există. Bucla while continuă cât timp intervalul este valid, adică st <= dr.

Capetele se actualizează cu m - 1, respectiv m + 1, nu cu m. Astfel excludem din interval elementul din mijloc, pe care tocmai l-am verificat, și ne asigurăm că intervalul se micșorează la fiecare pas. În caz contrar, căutarea ar putea intra într-o buclă infinită.

Să căutăm valoarea 23 în vectorul ordonat de mai jos (cu pozițiile numerotate de la 0):

pozitie:  0  1  2   3   4   5   6   7   8   9
valoare:  2  5  8  12  16  23  38  56  72  91

Dintr-un vector de 10 elemente, valoarea a fost găsită în doar 3 pași. Cu cât vectorul este mai mare, cu atât avantajul devine mai vizibil.

La fiecare pas, căutarea binară elimină jumătate din elementele rămase, așa că numărul de pași crește foarte lent în raport cu mărimea vectorului: complexitatea este de ordinul $O(\log_2 n)$. Pentru un vector cu un milion de elemente sunt suficienți aproximativ 20 de pași, în timp ce căutarea secvențială ar putea face un milion.

Căutarea binară este o metodă rapidă de regăsire a unei valori, cu condiția ca vectorul să fie ordonat. Înjumătățind intervalul la fiecare pas, ajunge la rezultat în foarte puține comparații. Reține diferența importantă: căutarea secvențială se aplică oricărui vector, dar parcurge până la n elemente, în timp ce căutarea binară cere un vector ordonat, însă lucrează în doar $O(\log_2 n)$ pași.