binary_search — există elementul?

De ce contează?

Cauți un cuvânt în dicționar. Nu o iei de la prima pagină — deschizi la mijloc, vezi dacă ești prea în față sau prea în spate, și înjumătățești de fiecare dată. În câțiva pași ai ajuns. binary_search face exact asta, automat.

Ce face `binary_search`

binary_search verifică dacă o valoare există într-un vector sortat. Întoarce true sau false. E versiunea gata făcută din STL a căutării binare.

bool gasit = binary_search(v, v + n, x);

Observația-cheie

Condiția obligatorie: vectorul trebuie să fie sortat. Pe un vector neordonat, rezultatul lui binary_search e nedefinit — poate spune „nu există" deși elementul e acolo.

De ce e atât de rapid

Căutarea liniară verifică element cu element: O(n). Căutarea binară înjumătățește intervalul la fiecare pas: O(log n). Pentru un milion de elemente, asta înseamnă ~20 de pași în loc de un milion.

Metodă	Pași pentru n = 1.000.000
căutare liniară	până la 1.000.000
căutare binară	~20

Cum decide la fiecare pas

Pe vectorul sortat v = {1, 3, 4, 6, 8, 11}, cauți 8:

interval [0..5], mij=2: v[2]=4 < 8  -> mergi dreapta, [3..5]
interval [3..5], mij=4: v[4]=8 == 8 -> gasit!

Compară cu mijlocul; dacă ținta e mai mare, elimină jumătatea stângă; dacă e mai mică, jumătatea dreaptă.

Exemplu complet

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int v[6] = {1, 3, 4, 6, 8, 11};   // SORTAT
    int n = 6;

    cout << binary_search(v, v + n, 8) << "\n";  // 1 (exista)
    cout << binary_search(v, v + n, 5) << "\n";  // 0 (nu exista)
    return 0;
}

Dacă vectorul nu e deja sortat, sortează-l întâi: sort(v, v + n);.

Vizualizare

Urmărește cum se înjumătățește intervalul de căutare la fiecare pas:

Indiciu

Folosește ← și → pentru a avansa pas cu pas. Observă cum mijlocul comparat decide care jumătate dispare.

Greșeli frecvente

Capcane la binary_search:

Vector nesortat: cea mai frecventă greșeală. Sortează întâi sau garantează ordinea.
Te aștepți la poziție: binary_search întoarce doar true/false. Pentru poziție folosește lower_bound.
Cauți într-un interval greșit: v, v + n acoperă tot vectorul; un capăt greșit lasă elemente neverificate.
Crezi că e mai rapid decât liniar pe vector mic nesortat: dacă oricum trebuie să sortezi pentru o singură căutare, sortarea costă O(n log n) — pentru o căutare unică, liniar (O(n)) poate fi mai ieftin. Binary search câștigă la multe căutări.

Recapitulare

binary_search spune dacă o valoare există într-un vector sortat, în O(log n).
Cere obligatoriu vector sortat; întoarce true/false, nu poziția.
Merită mai ales la multe căutări repetate; pentru o singură căutare pe vector mic, liniar poate fi suficient.