BAC 2026 Informatică: căutarea binară explicată pas cu pas

Căutarea binară este unul dintre algoritmii pe care merită să îi înțelegi, nu doar să îi memorezi. Apare în probleme cu tablouri unidimensionale ordonate și în exerciții în care trebuie să urmărești valorile unor variabile sau să compari eficiența unor soluții.

Pentru BAC 2026 și pregătirea admiterii la Informatică, ideea esențială este simplă: dacă elementele sunt ordonate, poți elimina aproximativ jumătate dintre candidați la fiecare pas. Hai să vedem de ce funcționează și cum scrii o implementare corectă în C++.

Ce problemă rezolvă căutarea binară

Avem un vector cu $n$ elemente, ordonat crescător în sens larg, adică fiecare element este mai mic sau egal cu următorul. Primim o valoare $x$ și vrem să aflăm dacă aceasta există în vector și, eventual, pe ce poziție.

O căutare secvențială verifică elementele unul câte unul. În cazul nefavorabil, ajunge să le examineze pe toate.

Căutarea binară procedează diferit:

1. Examinează elementul din mijlocul intervalului curent.
2. Dacă acesta este egal cu $x$, căutarea se încheie.
3. Dacă este mai mic decât $x$, continuă numai în jumătatea dreaptă.
4. Dacă este mai mare decât $x$, continuă numai în jumătatea stângă.

Condiția decisivă este ordonarea vectorului. Fără ea, comparația cu elementul din mijloc nu justifică eliminarea unei jumătăți.

De ce putem elimina elemente fără să le verificăm

Să presupunem că elementul din mijloc este 12, iar valoarea căutată este 19. Într-un vector ordonat crescător, toate elementele din stânga mijlocului sunt cel mult 12. Niciunul nu poate fi 19.

Așadar, nu facem o presupunere despre poziția rezultatului, ci folosim o proprietate sigură a datelor.

Intervalul de căutare și indicii

Vom folosi indexarea de la zero, specifică tablourilor C++. Pentru un vector cu $n$ elemente, indicii valizi sunt de la $0$ la $n-1$.

Notăm:

• st: limita din stânga a intervalului;
• dr: limita din dreapta;
• mij: indicele elementului din mijloc.

Intervalul este închis, deci include ambele capete. Inițial, st = 0 și dr = n - 1.

Calculăm mijlocul astfel:

$mij = st + \left\lfloor\frac{dr-st}{2}\right\rfloor$

În C++, pentru diferența nenegativă dr - st, împărțirea între întregi produce exact partea întreagă necesară. Formula evită calcularea sumei st + dr, care ar putea depăși capacitatea tipului întreg pentru indici foarte mari.

Repetăm căutarea cât timp st <= dr. Dacă st > dr, intervalul este gol, iar valoarea nu a fost găsită.

Implementare C++ pentru găsirea unei apariții

Funcția următoare întoarce indicele unei apariții a lui x sau -1 dacă valoarea lipsește. Presupunem că n reprezintă corect numărul de elemente și că vectorul este ordonat crescător.

Observă actualizările mij + 1 și mij - 1. Poziția mij a fost deja verificată, deci nu mai trebuie păstrată în interval după o comparație fără egalitate.

Dacă n = 0, avem inițial dr = -1. Bucla nu se execută, iar funcția întoarce -1, fără să acceseze tabloul.

Exemplu rezolvat pas cu pas

Considerăm vectorul:

Căutăm valoarea x = 23.

Pasul 1: verificăm mijlocul vectorului

Inițial, st = 0 și dr = 8.

$mij = 0 + \left\lfloor\frac{8-0}{2}\right\rfloor = 4$

Elementul a[4] este 16. Deoarece $16 < 23$, eliminăm indicii de la 0 la 4 și stabilim st = 5.

Intervalul rămas este [5, 8].

Pasul 2: restrângem căutarea spre stânga

Acum st = 5, dr = 8.

$mij = 5 + \left\lfloor\frac{8-5}{2}\right\rfloor = 6$

Elementul a[6] este 38. Deoarece $38 > 23$, eliminăm indicii de la 6 la 8 și stabilim dr = 5.

Intervalul rămas este [5, 5].

Pasul 3: verificăm ultimul candidat

Avem st = dr = 5, deci mij = 5. Elementul a[5] este 23, exact valoarea căutată.

Funcția întoarce indicele 5. Dacă enunțul cere poziția numerotată de la 1, răspunsul este poziția 6.

Pentru verificare, urmărește și căutarea valorii 24. După aceleași prime două etape, comparăm 24 cu a[5] = 23. Obținem st = 6, în timp ce dr = 5. Intervalul devine gol, deci rezultatul este -1.

De ce algoritmul este corect și eficient

La începutul fiecărei iterații păstrăm următoarea proprietate: dacă valoarea căutată există și nu am găsit-o deja, atunci ea se află în intervalul [st, dr].

Ordonarea ne permite să eliminăm numai poziții care nu pot conține valoarea căutată. În plus, după fiecare comparație fără egalitate, intervalul se micșorează strict. Astfel, algoritmul nu poate continua la nesfârșit.

După $k$ restrângeri, numărul de candidați este aproximativ $n/2^k$. De aici rezultă complexitatea temporală $O(\log n)$ în cazul nefavorabil, pentru $n$ pozitiv. Dacă găsim valoarea chiar la primul mijloc, timpul este $O(1)$.

Implementarea iterativă folosește memorie auxiliară $O(1)$: păstrează doar câteva variabile.

Atenție: dacă vectorul nu este ordonat, sortarea are propriul cost. Pentru o singură căutare, parcurgerea secvențială poate fi alegerea mai potrivită. Pentru multe căutări în aceleași date, sortarea urmată de căutări binare poate fi avantajoasă.

Greșeli frecvente

• Aplici algoritmul pe un vector neordonat. Nu mai există garanția că jumătatea eliminată nu conține rezultatul.
• Scrii st < dr în această implementare. Riști să nu verifici ultimul candidat. Pentru intervalul închis folosit aici, condiția este st <= dr.
• Actualizezi cu st = mij sau dr = mij. Intervalul poate rămâne neschimbat, provocând o buclă infinită.
• Inițializezi dr = n. Ultimul indice valid este n - 1, nu n.
• Confunzi indicele cu valoarea. Funcția întoarce locul unde a găsit elementul, nu elementul însuși.
• Consideri indicele 0 drept eșec. Zero este un rezultat valid. Verificarea absenței se face prin comparația cu -1.
• Presupui că obții prima apariție. Dacă există duplicate, această variantă poate întoarce oricare dintre aparițiile întâlnite.

Întrebări frecvente

Funcționează căutarea binară dacă există valori egale?

Da. Vectorul poate conține duplicate, atât timp cât rămâne ordonat. Pentru a găsi prima apariție, memorezi indicele când întâlnești egalitatea și continui căutarea în stânga. Pentru ultima apariție, continui în dreapta.

Pot folosi algoritmul pe un vector ordonat descrescător?

Da, dar trebuie inversată direcția eliminării. Dacă elementul din mijloc este mai mic decât valoarea căutată, continui în stânga, unde se află valorile mai mari. Codul prezentat mai sus presupune ordine crescătoare.

Cum verific rapid o soluție la examen?

Testează un vector cu un singur element, apoi caută primul element, ultimul element și o valoare absentă. Urmărește într-un tabel st, dr și mij. Verifică dacă intervalul se micșorează la fiecare pas și dacă fiecare acces folosește un indice valid.

Ce să reții pentru BAC și admitere

Înainte să scrii codul, precizează ordinea datelor, convenția de indexare și rezultatul cerut. Apoi păstrează consecvent aceeași definiție a intervalului.

Căutarea binară devine ușor de controlat când poți explica fiecare eliminare: ce poziții înlături și de ce nu pot conține răspunsul. Această justificare te ajută atât la implementare, cât și la grilele care cer urmărirea algoritmului.