Căutare binară — înjumătățește spațiul la fiecare pas

De ce contează?

Ai un dicționar cu 100.000 de cuvinte. Cauți „zebră". Deschizi la mijloc — ești la „M". Zebra e după M, deci arunci prima jumătate. Deschizi din nou la mijloc — ești la „S". Continui. După 17 pași găsești cuvântul. Dacă ai căuta pagină cu pagină, ai face 100.000 de pași. Asta este căutarea binară.

Condiția obligatorie

Căutarea binară funcționează doar pe șiruri sortate. Fără sortare, înjumătățirea nu are sens.

Algoritmul

Menții doi indici: st (stânga) și dr (dreapta). La fiecare pas:

Calculezi mijlocul: mid = (st + dr) / 2
Dacă a[mid] == target → găsit, returnezi mid
Dacă a[mid] < target → valoarea e în dreapta: st = mid + 1
Dacă a[mid] > target → valoarea e în stânga: dr = mid - 1
Repeți cât timp st <= dr

Observația-cheie

La fiecare pas, spațiul de căutare se înjumătățește. Un șir de 1.000.000 elemente necesită maximum log₂(1.000.000) ≈ 20 pași. Căutarea liniară ar face 1.000.000.

Implementare C++

#include <iostream>
using namespace std;

int cautareBinara(int a[], int n, int target) {
    int st = 0, dr = n - 1;
    while (st <= dr) {
        int mid = st + (dr - st) / 2; // evita overflow fata de (st+dr)/2
        if (a[mid] == target) return mid;
        if (a[mid] < target) st = mid + 1;
        else dr = mid - 1;
    }
    return -1; // nu exista
}

int main() {
    int a[] = {2, 5, 8, 12, 16, 23, 38, 45, 72, 91};
    int n = 10;
    cout << cautareBinara(a, n, 23) << endl;  // 5
    cout << cautareBinara(a, n, 10) << endl;  // -1
    return 0;
}

Indiciu

Scrie mid = st + (dr - st) / 2 în loc de (st + dr) / 2. Dacă st și dr sunt ambele ~2 miliarde, suma lor depășește int. Prima formă nu are acest risc.

Varianta recursivă

int cautareBinaraRec(int a[], int st, int dr, int target) {
    if (st > dr) return -1;
    int mid = st + (dr - st) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) return cautareBinaraRec(a, mid + 1, dr, target);
    return cautareBinaraRec(a, st, mid - 1, target);
}

Căutare binară pe răspuns

Căutarea binară nu se aplică doar pe șiruri — se poate aplica pe spațiul de răspunsuri al unei probleme:

„Care e cel mai mare x cu proprietatea P?"

Dacă P este monotonă (dacă P(x) e adevărat, P(x-1) e și el adevărat), poți face căutare binară pe x.

// exemplu: cel mai mare x astfel incat x*x <= n (radacina intreaga)
int radacinaIntreaga(int n) {
    int st = 0, dr = n;
    while (st < dr) {
        int mid = st + (dr - st + 1) / 2;
        if ((long long)mid * mid <= n) st = mid;
        else dr = mid - 1;
    }
    return st;
}

Greșeli frecvente

Greșeala clasică: bucla infinită când cauți maximul cu proprietatea P. Dacă mid = (st + dr) / 2 și setezi st = mid (nu mid + 1), când st + 1 == dr obții mid == st → bucla nu avansează. Soluție: mid = st + (dr - st + 1) / 2 (rotunjire în sus).

Complexitate

	Timp	Spațiu
Iterativ	O(log n)	O(1)
Recursiv	O(log n)	O(log n) stivă