Căutare binară — AlgoClar

De ce contează?

Ghicești un număr între 1 și 100. La fiecare încercare îți spun „mai mare" sau „mai mic". Strategia inteligentă: spui mereu mijlocul intervalului rămas. 50, apoi 25 sau 75... În ~7 întrebări nimerești orice număr. Asta e căutarea binară: înjumătățești la fiecare pas.

De ce funcționează doar pe sortat

Căutarea binară compară valoarea căutată cu elementul din mijloc. Dacă vectorul e sortat, comparația îți spune în ce jumătate să continui — cealaltă se aruncă. Pe date nesortate, comparația cu mijlocul nu spune nimic util.

Algoritm pas cu pas: caut 7 în

Indici st = 0, dr = 5. Mijlocul = (st+dr)/2:

st	dr	mij	v[mij]	comparație	continuăm
0	5	2	5	7 > 5	dreapta (st = 3)
3	5	4	9	7 < 9	stânga (dr = 3)
3	3	3	7	7 = 7	găsit la indicele 3

v	1	3	5	7	9	11
i	0	1	2	3	4	5
	st		mij			dr

Primul pas: compari 7 cu v[mij]=5. 7 e mai mare → arunci jumătatea stângă și cauți doar în dreapta.

Implementare C++

#include <iostream>
using namespace std;

int cautareBinara(int v[], int n, int cautat) {
    int st = 0, dr = n - 1;
    while (st <= dr) {
        int mij = st + (dr - st) / 2;   // evita overflow-ul lui st+dr
        if (v[mij] == cautat) return mij;       // gasit
        else if (v[mij] < cautat) st = mij + 1; // cautam in dreapta
        else dr = mij - 1;                      // cautam in stanga
    }
    return -1;                          // negasit
}

int main() {
    int v[] = {1, 3, 5, 7, 9, 11};
    cout << cautareBinara(v, 6, 7) << "\n";    // 3
    cout << cautareBinara(v, 6, 8) << "\n";    // -1
    return 0;
}

Observația-cheie

Mijlocul se scrie st + (dr - st) / 2, nu (st + dr) / 2. La indici mari, st + dr se poate sparge în int. Forma cu diferență ține valorile mici și dă același rezultat.

De ce e atât de rapidă

Fiecare pas elimină jumătate din candidați. Dintr-un milion ajungi la 1 în ~20 de pași. Comparativ, căutarea liniară ar verifica până la un milion de elemente. Câștigul crește exploziv cu n.

Complexitate

Metodă	Timp	Spațiu
căutare binară	O(log n)	O(1)
căutare liniară	O(n)	O(1)

Atenție: dacă vectorul nu e deja sortat, sortarea costă O(n log n) — o faci o singură dată, apoi toate căutările sunt O(log n).

Vizualizare

Urmărește cum intervalul [st, dr] se înjumătățește la fiecare pas și cum mijlocul se mută:

Indiciu

Observă că după fiecare comparație, fie st, fie dr sare lângă mijloc — jumătatea „greșită" dispare complet. De-aici vin cei ~log n pași.

Greșeli frecvente

Capcane reale la căutarea binară:

Vector nesortat: rezultatul e fără sens. Asigură-te că e sortat înainte.
Overflow la mijloc: (st + dr) / 2 se sparge la indici mari. Folosește st + (dr - st) / 2.
Buclă infinită: dacă nu actualizezi corect st/dr cu mij + 1 / mij - 1, intervalul nu se micșorează și bucla nu se termină.
Condiția st <= dr: cu st < dr ratezi cazul când răspunsul e chiar la st == dr.

De reținut

Căutarea binară merge doar pe vector sortat; înjumătățește intervalul la fiecare pas.
Mijloc = st + (dr - st) / 2 (anti-overflow); actualizează cu mij ± 1, condiție st <= dr.
O(log n) — ~20 de pași pentru un milion de elemente.