Căutarea binară: găsirea rapidă într-un vector sortat

Dacă cauți un cuvânt într-un dicționar, nu începi cu prima pagină: îl deschizi pe la mijloc și decizi dacă mergi la stânga sau la dreapta. Exact asta face căutarea binară. Pentru BAC informatică trebuie să știi trei lucruri despre ea: cum scrii bucla corect în C++, cum urmărești pașii pe un vector dat și câte comparații face cel mult. Toate trei apar la examen, de la grilele din Subiectul I până la problemele de la Subiectul III.

Condiția esențială: vectorul trebuie să fie sortat

Căutarea binară funcționează doar pe un vector ordonat (crescător, în exemplele de mai jos). Ideea: compari valoarea căutată x cu elementul din mijlocul zonei în care cauți. Dacă sunt egale, ai găsit-o. Dacă x e mai mare, știi sigur că nu poate fi în jumătatea stângă (toate elementele de acolo sunt mai mici), deci continui doar în dreapta. Dacă x e mai mic, continui în stânga. La fiecare pas, zona de căutare se înjumătățește.

Codul C++

#include <iostream>
using namespace std;

int main()
{
    int n, v[1001], x, i, st, dr, mij, poz = 0;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> v[i];
    cin >> x;
    st = 1; dr = n;
    while (st <= dr && poz == 0)
    {
        mij = (st + dr) / 2;
        if (v[mij] == x) poz = mij;
        else if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    if (poz != 0) cout << "gasit pe pozitia " << poz;
    else cout << "nu exista";
    return 0;
}

Trei detalii pe care trebuie să le scrii exact așa:

• st <= dr, nu st < dr: când zona are un singur element (st = dr), acel element trebuie și el verificat.
• st = mij + 1 și dr = mij - 1: elementul din mijloc a fost deja comparat, deci îl excludem. Dacă scrii st = mij, bucla se poate repeta la nesfârșit.
• mij = (st + dr) / 2 este împărțire întreagă, adică [(st+dr)/2] în pseudocod.

Urmărire pas cu pas

Fie vectorul cu n = 10 elemente:

poziția:  1  2  3   4   5   6   7   8   9  10
v:        2  5  8  12  16  23  38  56  72  91

Căutăm x = 23.

Elementele cu care s-a comparat x, în ordine: 16, 56, 23.

Căutăm x = 7 (care nu există în vector):

Acum st = 3 > dr = 2, bucla se oprește și se afișează „nu exista”. Observă unde a rămas st: pe poziția 3, adică exact locul în care ar trebui inserat 7 pentru ca vectorul să rămână sortat. Această proprietate e utilă în multe probleme.

De ce e O(log n)

La fiecare pas, zona de căutare se reduce cel puțin la jumătate. Pornind de la n elemente, după k pași rămân cel mult aproximativ n/2ᵏ. Căutarea se termină când zona devine goală, deci numărul maxim de pași este numărul de înjumătățiri până la 1, plus unul. Formula exactă pentru numărul maxim de comparații cu elemente ale vectorului este [log₂ n] + 1.

Un truc pentru calcul rapid: caută cea mai mare putere a lui 2 care nu depășește n. Pentru n = 1000, aceasta este 512 = 2⁹, deci maximul e 9 + 1 = 10. Pentru n = 10, puterea e 8 = 2³, deci 4 comparații — poți verifica pe vectorul de mai sus căutând 91: se compară cu 16, 56, 72 și 91.

Varianta recursivă

Căutarea binară apare des și ca subprogram recursiv, mai ales la itemii de recursivitate:

int caut(int v[], int st, int dr, int x)
{
    if (st > dr) return 0;
    int mij = (st + dr) / 2;
    if (v[mij] == x) return mij;
    if (v[mij] < x) return caut(v, mij + 1, dr, x);
    return caut(v, st, mij - 1, x);
}

Apelul inițial este caut(v, 1, n, x). Condiția de oprire st > dr corespunde zonei goale, adică valorii negăsite.

Prima poziție cu v[i] ≥ x

O variantă foarte utilă în probleme: nu vrei doar să știi dacă x există, ci prima poziție pe care se află o valoare mai mare sau egală cu x (de exemplu, ca să numeri câte valori sunt mai mici decât x). Nu te oprești la prima egalitate, ci reții poziția candidat și continui spre stânga:

st = 1; dr = n; poz = n + 1;
while (st <= dr)
{
    mij = (st + dr) / 2;
    if (v[mij] >= x) { poz = mij; dr = mij - 1; }
    else st = mij + 1;
}
// valorile mai mici decât x sunt pe pozițiile 1..poz-1

Pe vectorul de mai sus, pentru x = 20 se obține poz = 6 (v[6] = 23), deci 5 valori sunt mai mici decât 20. Dacă toate valorile sunt mai mici decât x, poz rămâne n + 1.