1
1. Conditia si intuitia: de ce injumatatim?
Cautarea binara (binary search) gaseste un element intr-un sir sortat in timp O(log n), comparand cu elementul din mijlocul intervalului curent si eliminand la fiecare pas jumatatea imposibila.
Analogie: Dictionar tiparit
Cand cauti cuvantul "masina" intr-un dictionar de 1000 de pagini, nu citesti pagina 1, 2, 3... Deschizi la pagina 500, vezi "L", stii ca "M" e dupa — deschizi la 750 etc. Asta e cautarea binara: exploatezi ordinea pentru a elimina jumatati.
De ce trebuie sortat?
La pasul "mijloc=56 > 23, deci 23 nu poate fi dupa pozitia 7" — acest rationament e valid NUMAI daca sirul e sortat crescator. Pe un sir nesortat, 23 ar putea fi oriunde.
2
2. Algoritmul pas cu pas: traseul complet
Invariant: elementul cautat, daca exista, se afla mereu in [stanga, dreapta]. La fiecare pas calculam mijloc, comparam si reducem intervalul.
Trace: cautam target=23 in v=[2,5,8,12,16,23,38,56,72,91]
stanga=0, dreapta=9 Pas 1: mijloc=(0+9)/2=4, v[4]=16 < 23 -> stanga=5 Pas 2: mijloc=(5+9)/2=7, v[7]=56 > 23 -> dreapta=6 Pas 3: mijloc=(5+6)/2=5, v[5]=23 == 23 -> GASIT la index 5! Numar de comparatii: 3 (cautare liniara ar fi facut 6)
// Pseudocod cautare binara
stanga ← 0 ; dreapta ← n - 1
cat timp stanga <= dreapta executa
mijloc ← (stanga + dreapta) / 2
daca v[mijloc] = target atunci returneaza mijloc
altfel daca v[mijloc] < target atunci stanga ← mijloc + 1
altfel dreapta ← mijloc - 1
returneaza -1
stanga ← 0 ; dreapta ← n - 1
cat timp stanga <= dreapta executa
mijloc ← (stanga + dreapta) / 2
daca v[mijloc] = target atunci returneaza mijloc
altfel daca v[mijloc] < target atunci stanga ← mijloc + 1
altfel dreapta ← mijloc - 1
returneaza -1
3
3. Implementare in Python
# Cautare binara - returneaza indexul sau -1 def cautare_binara(v, n, target): stanga = 0 dreapta = n - 1 while stanga <= dreapta: mijloc = (stanga + dreapta) // 2 if v[mijloc] == target: return mijloc elif v[mijloc] < target: stanga = mijloc + 1 else: dreapta = mijloc - 1 return -1 v = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] n = len(v) print(cautare_binara(v, n, 23)) # 5 print(cautare_binara(v, n, 10)) # -1
Output real (rulat cu python):
5 -1
4
4. Complexitatea O(log n)
La fiecare pas, intervalul se injumatateste. Dupa k pasi, intervalul are n/2^k elemente. Cand n/2^k < 1 (adica k > log2(n)), am terminat. Numarul de pasi este O(log n).
Comparatie: cautare liniara O(n) vs binara O(log n)
n = 10: liniar=10 pasi, binar~ 4 pasi n = 100: liniar=100 pasi, binar~ 7 pasi n = 1000: liniar=1000 pasi, binar~10 pasi n = 1.000.000: liniar=1M pasi, binar~20 pasi
Calcul real (python, import math):
log2(10) = 3.3219, max_pasi = 4
La BAC, pentru analiza eficientei: T(n) = O(log n), mai eficienta decat cautarea liniara O(n).
5
5. Implementare in C++ EXCLUSIV INTENSIV
⚡ Sectiune doar pentru intensiv informatica
La profilul intensiv se cere implementarea in C++. Diferente fata de Python: tipuri declarate explicit (int, vector<int>), formula anti-overflow pentru mijloc, -1 ca valoare santinela.
#include <iostream> #include <vector> using namespace std; // Returneaza indexul lui target sau -1 daca nu exista int cautare_binara(vector<int>& v, int target) { int stanga = 0; int dreapta = (int)v.size() - 1; while (stanga <= dreapta) { int mijloc = stanga + (dreapta - stanga) / 2; // anti-overflow if (v[mijloc] == target) return mijloc; else if (v[mijloc] < target) stanga = mijloc + 1; else dreapta = mijloc - 1; } return -1; } int main() { vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}; cout << cautare_binara(v, 23) << endl; // 5 cout << cautare_binara(v, 10) << endl; // -1 return 0; }
Output real (compilat g++ -std=c++17, rulat):
5 -1
6
6. Variante: lower_bound si upper_bound EXCLUSIV INTENSIV
⚡ Sectiune avansata - intensiv informatica
In competitii si BAC la profil intensiv apar variantele lower_bound si upper_bound, esentiale pentru a numara aparitii sau a gasi intervale in siruri sortate.
lower_bound(target): primul indice i cu v[i] >= target.
upper_bound(target): primul indice i cu v[i] > target.
Numarul de aparitii ale lui target = upper_bound(t) - lower_bound(t).
upper_bound(target): primul indice i cu v[i] > target.
Numarul de aparitii ale lui target = upper_bound(t) - lower_bound(t).
# lower_bound: primul indice >= target def lower_bound(v, n, t): s, d = 0, n while s < d: m = (s + d) // 2 if v[m] < t: s = m + 1 else: d = m return s v2 = [1, 3, 3, 5, 7, 9, 9, 11] print(lower_bound(v2, 8, 3)) # 1 print(lower_bound(v2, 8, 4)) # 3 print(lower_bound(v2, 8, 12)) # 8
Output real (rulat cu python):
1 3 8
C++ lower_bound manual (EXCLUSIV INTENSIV) - output real g++ -std=c++17: lb(3)=1, lb(4)=3, lb(12)=8
int lb(vector<int>& v, int t) { int s = 0, d = (int)v.size(); while(s < d) { int m = s + (d-s) / 2; if(v[m] < t) s = m + 1; else d = m; } return s; } // Echivalent STL: lower_bound(v.begin(), v.end(), t) - v.begin()