Ce vei învăța astăzi?
După această lecție vei înțelege când putem folosi căutarea binară, cum funcționează algoritmul cu doi indici (variabile care marchează capetele intervalului de căutare) st și dr și de ce este mult mai eficientă decât căutarea secvențială.
Ce este căutarea binară?
Definiție: Căutarea binară este un algoritm de căutare care se aplică pe un tablou sortat. La fiecare pas, intervalul de căutare se înjumătățește, comparând valoarea căutată cu elementul din mijloc.
Deoarece tabloul este sortat, dacă elementul din mijloc este mai mic decât x, atunci x nu poate fi în jumătatea stângă și o eliminăm. La fel în caz contrar.
Analogia din viața reală:
Gândește-te la un dicționar: nu îl parcurgi cuvânt cu cuvânt. Îl deschizi la mijloc și, dacă litera căutată este mai înainte sau mai în urmă, continui doar în jumătatea potrivită.
| Caracteristică | Căutare secvențială | Căutare binară |
|---|---|---|
| Tablou necesar | oricare | sortat |
| Număr de pași pentru n = 1000 | până la 1000 | aproximativ 10 |
| Complexitate | O(n) | O(log2 n) |
Algoritmul cu doi indici
Folosim doi indici: st (stânga) și dr (dreapta), care delimitează intervalul de căutare. Indicele din mijloc este mij = (st + dr) / 2. Cât timp st <= dr, comparăm a[mij] cu x și micșorăm intervalul.
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (poz == 0)
cout << -1;
else
cout << poz;
return 0;
}
Observă: poz = 0 înseamnă că valoarea nu a fost găsită. Când a[mij] < x, căutăm în dreapta (st = mij + 1); altfel, în stânga (dr = mij - 1).
Pas cu pas: căutarea binară pe un exemplu
Exemplu: tabloul 1 3 5 7 9 11, căutăm x = 7
Pașii algoritmului (n = 6)
Observă: în doar 3 pași am găsit valoarea într-un tablou cu 6 elemente. Cu căutarea secvențială am fi verificat 4 elemente.
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij;
bool gasit = false;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
while (st <= dr && !gasit) {
mij = (st + dr) / 2;
if (a[mij] == x) {
gasit = true;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (gasit)
cout << mij;
else
cout << -1;
return 0;
}
Exercițiu de completare
Completează enunțul cu cuvintele potrivite:
Căutarea binară se aplică doar pe tablouri ______. La fiecare pas, intervalul de căutare se ______, iar numărul de pași este aproximativ ______.
Bancă de cuvinte:
Exercițiu de completare 2
Completează afirmațiile despre algoritm:
Bucla se repetă cât timp ______. Indicele din mijloc se calculează cu ______, iar elementul comparat cu x este ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - căutarea binară:
1. Căutarea binară cere ca tabloul să fie:
2. La fiecare pas, intervalul de căutare:
3. Pentru un tablou cu 1024 de elemente, numărul maxim de pași ai căutării binare este aproximativ:
st < dr în loc de st <= dr, intervalul cu un singur element nu mai este verificat și poți afișa -1 chiar dacă valoarea se află în tablou.Aprofundare
De ce mij = (st + dr) / 2 și nu altceva? Indicele din mijloc împarte intervalul în două jumătăți cât mai egale, iar după fiecare comparație aruncăm exact jumătate din interval. Pentru un tablou cu n elemente, numărul maxim de pași este log2(n) + 1. Practic, dintr-un milion de elemente găsim orice valoare în cel mult 20 de comparații - de aceea căutarea binară este algoritmul preferat atunci când datele sunt sortate.
Capcana indicilor st și dr: dacă înlocuim condiția st <= dr cu st < dr, atunci când intervalul are un singur element nu mai verificăm deloc, iar răspunsul poate fi greșit. De asemenea, la actualizări trebuie să folosim st = mij + 1 și dr = mij - 1; dacă punem doar st = mij, iar mij nu conține valoarea căutată, bucla poate rula la nesfârșit (buclă infinită), mai ales când st == dr.
Variantă fără break, cu semnalizator: unele soluții folosesc o variabilă bool gasit în loc de break. Ambele variante sunt corecte și acceptate la BAC; important este să păstrezi poziția găsită înainte de oprire, pentru că la ieșirea din buclă mij poate să nu mai fie poziția valabilă dacă intervalul s-a modificat după găsire.
Când NU folosim căutarea binară: dacă tabloul nu este sortat, căutarea binară poate răspunde greșit - exemplu clasic: tabloul 1 3 2 4 și x = 2. Sortarea în prealabil (cu un algoritm de tip O(n^2)) ar costa mai mult decât o căutare secvențială. Regula: binele căutării binare apare doar dacă lista este deja sortată, cum se întâmplă la notele ordonate dintr-un catalog sau la prețurile sortate dintr-un magazin online.
PbInfo - Căutare binară
Enunț:
Cerință: Se dă un tablou cu n numere naturale, sortat crescător, și o valoare x. Să se afișeze poziția pe care se găsește x sau valoarea -1 dacă nu există.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n valori sortate, apoi valoarea x.
Date de ieșire:
Programul va afișa poziția lui x în tablou (prima poziție, numerotată de la 1) sau -1 dacă valoarea nu există.
Restricții și precizări:
1 <= n <= 100000, valorile din tablou sunt numere naturale sortate crescător.
Exemplu:
Intrare:
6 1 3 5 7 9 11 7
Ieșire:
4
Cum gândim soluția:
- Citim tabloul sortat și valoarea
x - Inițializăm
st = 1șidr = n - Repetăm cât timp
st <= dr: calculămmijși comparăma[mij]cux - Afișăm poziția găsită sau
-1
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (poz == 0)
cout << -1;
else
cout << poz;
return 0;
}
Ce învățăm: căutarea binară reduce intervalul la jumătate la fiecare pas, iar poz reține poziția găsită sau 0 dacă valoarea lipsește.
PbInfo - Primul element mai mare sau egal cu x
Enunț:
Cerință: Se dă un tablou cu n numere naturale, sortat crescător, și o valoare x. Să se afișeze poziția primului element cu valoarea mai mare sau egală cu x, sau -1 dacă un astfel de element nu există.
Date de intrare:
Programul citește de la tastatură numărul n, apoi cele n valori sortate, apoi valoarea x.
Date de ieșire:
Programul va afișa poziția primului element cu valoare >= x sau -1.
Restricții și precizări:
1 <= n <= 100000, valorile din tablou sunt numere naturale sortate crescător.
Exemplu:
Intrare:
6 1 3 5 7 9 11 6
Ieșire:
4
Cum gândim soluția:
- Căutăm prima poziție cu
a[mij] >= x - Când găsim o astfel de poziție, o reținem și continuăm căutarea în stânga
- Inițializăm
poz = n + 1; dacă rămâne neschimbată, afișăm-1
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
poz = n + 1;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] >= x) {
poz = mij;
dr = mij - 1;
} else {
st = mij + 1;
}
}
if (poz == n + 1)
cout << -1;
else
cout << poz;
return 0;
}
Ce învățăm: căutarea primului element cu o proprietate se face reținând candidatul și continuând spre stânga, iar poz = n + 1 marchează lipsa unui rezultat.
Exercițiul Practic: Căutarea binară în acțiune
Sarcini de lucru
Completează următoarele sarcini pentru a-ți consolida căutarea binară
Sarcina 1: Caută valoarea 6
Cerință: Scrie un program C++ care citește tabloul sortat 2 4 6 8 10 (n = 5) și valoarea x = 6, apoi afișează poziția lui 6 folosind căutarea binară.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int main() {
int a[6] = {0, 2, 4, 6, 8, 10};
int x = 6, st, dr, mij, poz = 0;
st = 1;
dr = 5;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
cout << poz;
return 0;
}
Verifică: x = 6 se găsește pe poziția 3. Tabloul a fost declarat cu poziția 0 nefolosită, iar căutarea folosește pozițiile 1-5.
Sarcina 2: Numără comparațiile
Cerință: Modifică programul de la Sarcina 1 astfel încât să numere de câte ori s-a calculat indicele mij în bucla while și să afișeze atât poziția, cât și numărul de pași.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int a[6] = {0, 2, 4, 6, 8, 10};
int x = 6, st, dr, mij, poz = 0, pasi = 0;
st = 1;
dr = 5;
while (st <= dr) {
mij = (st + dr) / 2;
pasi++;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
cout << poz << " " << pasi;
return 0;
}
Verifică: pentru x = 6 se efectuează 2 pași până la găsirea poziției 3, mult mai puțin decât la căutarea secvențială.
Scrie pe caiet - De reținut
Titlul lecției
Ora 4: Liste sortate - căutarea binară
Definiția lecției
Căutarea binară este un algoritm de căutare care se aplică pe un tablou sortat și găsește o valoare înjumătățind intervalul de căutare la fiecare pas. Folosim doi indici: st (stânga) și dr (dreapta), care delimitează zona în care mai poate fi valoarea căutată, plus indicele din mijloc, mij = (st + dr) / 2. Cât timp st <= dr, comparăm a[mij] cu x: dacă sunt egale, am găsit valoarea; dacă a[mij] < x, continuăm în dreapta cu st = mij + 1; altfel, continuăm în stânga cu dr = mij - 1. Dacă bucla se termină fără a găsi valoarea, afișăm -1. Complexitatea este O(log2 n), mult mai bună decât O(n) a căutării secvențiale, ceea ce face algoritmul esențial pentru date sortate cu restricții mari.
Definiții esențiale
- Căutarea binară este un algoritm de căutare aplicat pe un tablou sortat, care înjumătățește intervalul de căutare la fiecare pas.
- Indicii folosiți:
st(stânga),dr(dreapta) șimij = (st + dr) / 2(mijlocul). - Complexitatea: O(log2 n) comparații, față de
O(n)la căutarea secvențială. - Dacă
a[mij] < x, căutăm în dreapta (st = mij + 1); altfel, în stânga (dr = mij - 1).
Algoritmul cheie - pseudocod
Algoritmul cheie - cod C++
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
Greșeli comune de evitare
- Condiția
st < drîn loc dest <= dr: intervalul cu un singur element nu mai este verificat. - Actualizarea
st = mijsaudr = mij: poate produce buclă infinită; foloseștemij + 1șimij - 1. - Căutarea binară pe un tablou nesortat: rezultatul poate fi greșit, deși programul rulează.
Exemplu practic
Un magazin online are catalogul produselor sortat după preț, de la cel mai mic la cel mai mare. Un client caută un produs care costă exact x lei; programul trebuie să răspundă instant, fără să parcurgă toate cele n produse. Căutarea binară rezolvă problema în aproximativ log2 n comparații.
#include <iostream>
using namespace std;
int main() {
int n, a[100005], x, i, st, dr, mij, poz = 0;
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
cin >> x;
st = 1;
dr = n;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij] == x) {
poz = mij;
break;
} else if (a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if (poz == 0)
cout << -1;
else
cout << poz;
return 0;
}
Pentru un catalog cu 1000 de prețuri sortate, programul găsește prețul cerut în cel mult 10 comparații, față de până la 1000 la căutarea secvențială.
Sfaturi practice și trucuri
- Verifică întotdeauna cazurile limită:
xmai mic decât toate, mai mare decât toate, prezent o singură dată. - Memorează poziția cu
poz = 0ca „negăsit" - este convenția folosită în majoritatea baremelor. - Dacă ai dubii, rulează algoritmul pe hârtie cu un tablou mic înainte de a-l scrie în C++.