Căutare binară
Algoritm eficient de căutare într-un șir sortat prin înjumătățirea intervalului.
Căutarea secvențială
Notă: Atenție: această lecție folosește vectori (tablouri unidimensionale). Dacă nu ai parcurs încă lecția "Tablouri Unidimensionale (Vectori)", fă-o mai întâi.
Înainte de căutarea binară, trebuie să înțelegi varianta simplă: căutarea secvențială. Parcurgi vectorul element cu element până găsești ce cauți sau ajungi la final.
Scheletul general
#include <iostream>
using namespace std;
int main() {
int n, x, v[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
cin >> x; // elementul căutat
bool gasit = false;
int pozitie = -1;
for (int i = 0; i < n; i++) {
if (v[i] == x) {
gasit = true;
pozitie = i;
}
}
if (gasit)
cout << "gasit pe pozitia " << pozitie;
else
cout << "negasit";
return 0;
}Oprire la prima apariție cu break
Dacă vrei să te oprești la prima apariție în loc să parcurgi tot vectorul:
bool gasit = false;
int pozitie = -1;
for (int i = 0; i < n; i++) {
if (v[i] == x) {
gasit = true;
pozitie = i;
break;
}
}Când folosești căutarea secvențială
- Vectorul nu este sortat
- Vectorul e mic și eficiența nu contează
- Cauți toate aparițiile unui element, nu doar prima
Dezavantajul căutării secvențiale
În cel mai rău caz, parcurgi toți cei n pași. Dacă n = 1.000.000, faci 1.000.000 de comparații. Căutarea binară rezolvă exact această problemă, dar necesită vectorul sortat.
Notă: La BAC: căutarea secvențială este tiparul de bază pentru parcurgerea unui vector. O folosești ori de câte ori trebuie să verifici sau să prelucrezi fiecare element în parte.
Ideea din spatele căutării binare
Căutarea binară funcționează doar pe vectori sortați. Ideea e să elimini jumătate din elementele rămase la fiecare pas.
Analogie
Gândește-te că ai un dicționar și cauți cuvântul "mașină". Nu începi de la pagina 1 — deschizi la mijloc, vezi că ești la "N", deci mergi înapoi. Deschizi la mijlocul părții rămase, ești la "H", mergi înainte. Repeți până găsești.
Cum funcționează
Menții trei indici: st (stânga), dr (dreapta) și mij (mijlocul). La fiecare pas:
- Dacă
v[mij] == x: am găsit - Dacă
v[mij] < x: x e în jumătatea dreaptă,st = mij + 1 - Dacă
v[mij] > x: x e în jumătatea stângă,dr = mij - 1
Repeți până găsești sau st > dr.
De ce e eficientă
La fiecare pas elimini jumătate din elementele rămase. Pentru n = 1.000.000 ai nevoie de maximum 20 de pași (log₂(1.000.000) ≈ 20). Față de 1.000.000 la căutarea secvențială.
Algoritmul de căutare binară
Scheletul general
#include <iostream>
using namespace std;
int main() {
int n, x, v[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
cin >> x;
int st = 0, dr = n - 1, pozitie = -1;
while (st <= dr) {
int mij = (st + dr) / 2;
if (v[mij] == x) {
pozitie = mij;
break;
} else if (v[mij] < x) {
st = mij + 1; // x e în dreapta
} else {
dr = mij - 1; // x e în stânga
}
}
if (pozitie != -1)
cout << "gasit pe pozitia " << pozitie;
else
cout << "negasit";
return 0;
}Notă: Atenție: inițializezist = 0șidr = n - 1, nudr = n. Indicii vectorului merg de la 0 la n-1.
Notă: Atenție: condiția buclei estest <= dr, nust < dr. Dacă aist == drmai ai un element de verificat.
Urmărire pas cu pas
Date: v = [1, 3, 5, 7, 9, 11, 13], n=7, x=7
| Pas | st | dr | mij | v[mij] | Comparație | Acțiune |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 7 == 7 | găsit! pozitie=3 |
Găsit din primul pas pentru că 7 e exact la mijloc.
Date: v = [1, 3, 5, 7, 9, 11, 13], n=7, x=11
| Pas | st | dr | mij | v[mij] | Comparație | Acțiune |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 11 > 7 | st = 4 |
| 2 | 4 | 6 | 5 | 11 | 11 == 11 | găsit! pozitie=5 |
Date: v = [1, 3, 5, 7, 9, 11, 13], n=7, x=6
| Pas | st | dr | mij | v[mij] | Comparație | Acțiune |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 6 < 7 | dr = 2 |
| 2 | 0 | 2 | 1 | 3 | 6 > 3 | st = 2 |
| 3 | 2 | 2 | 2 | 5 | 6 > 5 | st = 3 |
| stop | 3 | 2 | — | — | st > dr, ieșim | negăsit |
Exerciții mixte și recapitulare
Tiparul căutării binare: de memorat
st = 0, dr = n - 1, pozitie = -1
while (st <= dr):
mij = (st + dr) / 2
dacă v[mij] == x: pozitie = mij, break
dacă v[mij] < x: st = mij + 1
altfel: dr = mij - 1Exercițiu 1 — Căutare binară cu afișarea numărului de pași
Problemă: Se dă un vector sortat și un element x. Afișați dacă x se află în vector și câți pași a folosit căutarea binară.
#include <iostream>
using namespace std;
int main() {
int n, x, v[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
cin >> x;
int st = 0, dr = n - 1, pozitie = -1, pasi = 0;
while (st <= dr) {
pasi++;
int mij = (st + dr) / 2;
if (v[mij] == x) {
pozitie = mij;
break;
} else if (v[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (pozitie != -1)
cout << "gasit pe pozitia " << pozitie << " in " << pasi << " pasi";
else
cout << "negasit dupa " << pasi << " pasi";
return 0;
}Exemplu: v=[1,3,5,7,9,11,13], x=11 → gasit pe pozitia 5 in 2 pasi
Exercițiu 2 — Câte apariții are x într-un vector sortat
Problemă: Se dă un vector sortat și un element x. Afișați de câte ori apare x în vector.
Notă: Aici nu folosim căutare binară — căutarea binară nu găsește toate aparițiile direct. Folosim căutarea secvențială:
#include <iostream>
using namespace std;
int main() {
int n, x, v[100], contor = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
cin >> x;
for (int i = 0; i < n; i++)
if (v[i] == x) contor++;
cout << contor;
return 0;
}Exemplu: v=[1,3,3,3,5,7], x=3 → 3
Notă: Observă că pentru numărarea aparițiilor, chiar și pe un vector sortat, căutarea secvențială e mai simplă și corectă.
Exercițiu 3 — Căutare secvențială pe vector nesortat
Problemă: Se dă un vector și un element x. Afișați toate pozițiile unde apare x.
#include <iostream>
using namespace std;
int main() {
int n, x, v[100];
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i];
cin >> x;
bool gasit = false;
for (int i = 0; i < n; i++) {
if (v[i] == x) {
cout << i << " ";
gasit = true;
}
}
if (!gasit)
cout << "negasit";
return 0;
}Exemplu: v=[3,1,3,5,3], x=3 → 0 2 4
Notă: La BAC: când problema cere toate pozițiile unui element, folosești întotdeauna căutare secvențială, indiferent dacă vectorul e sortat sau nu.