
Căutare binară în C++
În multe situații avem un șir de elemente (cum ar fi numere naturale) și suntem nevoiți să verificăm dacă o anumită valoare se găsește sau nu în șir (și eventual să găsim și poziția pe care se află).
Un algoritm clasic parcurge elementele de la început la final și compară
valoarea de căutat cu fiecare element în parte, pe rând. Acesta este un
algoritm brut și ineficient, în special pentru un număr mare de elemente,
complexitatea sa
fiind O(n)
.
Pentru un șir de valori ordonate crescător, putem să ne folosim de un algoritm
de căutare binară, care reușește să răspundă la întrebarea propusă în
doar O(log2 n)
, un timp mult mai bun.
Valoarea lui n |
Număr maxim de pași folosind căutarea normală (secvențială) | Număr maxim de pași folosind căutarea binară |
---|---|---|
10 |
10 |
4 (60% mai rapid) |
100 |
100 |
7 (93% mai rapid) |
1.000.000 |
1.000.000 |
20 (99.998% mai rapid) |
Cum funcționează algoritmul căutarea binară?
Algoritmul de căutare binară ia șirul (să îl numim a
, cu elementele pe
pozițiile de la 1
la n
) cu valori ordonate (de obicei crescător) și
valoarea căutată, x
. Începe prin a compara elementul din mijlocul șirului
lui a
cu x
. Există trei situații posibile:
- Valoarea din mijloc,
a[mij]
, este chiar egală cux
. În acest caz ne oprim și marcăm că am găsit elementul; - Valoarea din mijloc,
a[mij]
, este mai mică decâtx
. Atunci, deoarece șirul este sortat crescător, nu are rost să mai verificăm elementele din stânga luia[mij]
(cu pozițiile de la1
lamij - 1
), căci categoricx
este mai mare decât toate acestea. Așadar considerăm doar elementele șirului de pe pozițiilemij + 1
până lan
și repetăm algoritmul pe această jumătate, luând mijlocul acestei secvențe; - Valoarea din mijloc,
a[mij]
, este mai mare decâtx
. Atunci, similar ca la al doilea caz, nu are rost să verificăm elementele din dreapta luia[mij]
, așadar am redus șirul la jumătate.
Dacă, la final, am ajuns pe o poziție a cărei valoare diferă de x
, atunci
x
cu siguranță nu se găsește în șir.
Vedem că algoritmul acesta este mult mai eficient, întrucât la fiecare pas împărțim șirul în două, reducând semnificativ numărul de elemente de comparat.
Exemplu vizual: căutare binară
Să luăm următorul șir, unde căutăm valoarea x = 35
.
i |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
a[i] |
10 | 23 | 35 | 37 | 54 | 67 | 84 |
Luăm poziția din mijloc: (1 + 7) / 2 = 4
. Comparăm valoarea sa, 37
, cu x = 35
. Vedem că este mai mare, așadar nu ne mai interesează elementele din
dreapta acestui element (le marcăm cu roșu).
i |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
a[i] |
10 | 23 | 35 | 37 | 54 | 67 | 84 |
Din partea rămasă a șirului (elementele de pe pozițiile de la 1
la 3
),
luăm mijlocul, (1 + 3) / 2 = 2
. Cum 23
este mai mic decât 35
, tăiem
elementele de pe pozițiile 1
și 2
.
i |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
a[i] |
10 | 23 | 35 | 37 | 54 | 67 | 84 |
Am rămas cu elementul de pe poziția 3
, adică 35
. Vedem că este chiar egal
cu x
, așadar ne oprim și spunem că am găsit elementul.
i |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
a[i] |
10 | 23 | 35 | 37 | 54 | 67 | 84 |
În loc să facem un maxim de 7
pași (în cel mai rău caz, folosind căutarea
secvențială), am făcut doar 3
.
Implementarea căutării binare în cod
Cea mai simplă metodă de a implementa căutarea binară este să ne folosim de
doi indici suplimentari, st
și dr
, care să ne spună în ce interval ne
aflăm într-un anumit moment. La început, st = 1
și dr = n
, însă modificăm
aceste valori pe parcurs cu cât tăiem din valori.
Calcularea poziției de mijloc este foarte ușoară: tot ce trebuie să facem este
să calculăm media aritmetică a celor două poziții: mij = (st + dr) / 2
.
Căutarea binară în C++
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim valorile în ordinea: lungimea șirului, șirul și valoarea căutată
int a[100], n, x;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
int st = 1, dr = n;
int gasit = -1; //Poziția pe care se află x, respectiv -1 dacă nu se găsește
while(st <= dr) { //Cât timp avem un interval valid
int mij = (st + dr) / 2;
if(a[mij] == x) {
gasit = mij;
break;
} else if(a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
if(gasit == -1) {
cout << "Nu am gasit valoarea " << x << " in sir!";
} else {
cout << "Valoarea " << x << " se gaseste in sir pe pozitia " << gasit << "!";
}
return 0;
}
În această lecție puteți urmări o rezolvare recursivă, pentru clasa a X-a.
Problemă rezolvată
Căutare binară a mai multor valori
Dându-se un șir a
cu n
numere naturale, ordonate crescător, să se verifice
dacă alte m
valori se găsesc sau nu în șir. Încarcă soluția ta
aici.
Exemplu: Pentru n = 6
, șirul a = (2, 4, 7, 8, 8, 9)
, și cele m = 5
valori: 1, 2, 8, 10, 9
, se afișează 0 1 1 0 1
.
Rezolvare: Pentru fiecare dintre cele m
numere, căutăm binar și afișăm
0
sau 1
, în funcție de verdict.
#include <iostream>
using namespace std;
int n, a[100001], m, x;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> m;
for(int i = 1; i <= m; i++) {
cin >> x;
int gasit = 0, st = 1, dr = n;
while(st <= dr) {
int mij = (st + dr) / 2;
if(a[mij] == x) {
gasit = 1;
break;
} else if(a[mij] < x) {
st = mij + 1;
} else {
dr = mij - 1;
}
}
cout << gasit << " ";
}
return 0;
}
Exerciții propuse
Completează următoarele secvențe de cod:
Să se caute binar valoarea q
în șirul a
:
int st = 1, dr = n;
int gasit = -1;
while(!(st ??? dr)) {
int mij = (st + dr) / 2;
if(a[mij] == q) gasit = mij;
else if(a[mij] < q) st = mij + 1;
else dr = mij - 1;
}
Să se caute binar valoarea x
în șirul a
, cu elementele în ordine
descrescătoare:
int st = 1, dr = n;
int gasit = -1;
while(st <= dr) {
int mij = (st + dr) / 2;
if(a[mij] == x) gasit = mij;
else if(a[mij] ??? x) st = mij + 1;
else dr = mij - 1;
}
Probleme propuse
Setul de probleme 145 nu a fost găsit.
Căutare binară pentru olimpiadă
Atenție la indici
Dacă valorile pentru st
și dr
sunt valori mari și există riscul de a ieși
din tipul de date int
atunci când calculăm valoarea de mijloc (întrucât
facem suma valorilor st
și dr
), o alternativă este: mij = st + (dr - st) / 2
.
Tip de problemă comună
Pentru olimpiade și concursuri, un tip de problemă care apare des cere găsirea unei valori minime/maxime pentru care o anumită proprietate este respectată: de pildă, problema Buldo de la OJI 2020, clasa a IX-a.
Aici, putem să luăm ca arie de valori pentru H
ce trebuie calculat toate
numerele de la 1
până la 1.000.000.000
. Cum după o anumită valoare
proprietatea nu se mai respectă, putem să căutăm binar cea mai mare valoare
H
pentru care proprietatea este respectată.
Pe aceeași idee există multe alte probleme date la concursuri și olimpiade (chiar și naționale).
Funcții din STL
Există câteva funcții care implementează deja algoritmul de căutare binară.
Acestea se găsesc în biblioteca <algorithm>
și pot returna următoarele:
#include <algorithm>
...
binary_search(a + 1, a + n + 1, x); //true, dacă x se găsește în a, respectiv false în caz contrar
lower_bound(a + 1, a + n + 1, x); //Pointer către cea mai din stânga poziție din a, egală cu x
upper_bound(a + 1, a + n + 1, x); //Pointer către cea mai din dreapta poziție din a, egală cu x
Bibliografie sau alte resurse
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Cuprinsul lecției
Cum funcționează algoritmul căutarea binară?Exemplu vizual: căutare binarăImplementarea căutării binare în codCăutarea binară în C++Problemă rezolvatăCăutare binară a mai multor valoriExerciții propuseProbleme propuseCăutare binară pentru olimpiadăAtenție la indiciTip de problemă comunăFuncții din STLBibliografie sau alte resurseCreează-ți un cont InfoAs și primești…
- Acces la sute de lecții de calitate, cu animații și exerciții
- Acces la peste 800 de probleme de informatică
- Indicații și rezolvări pentru fiecare problemă
- Totul 100% gratuit!
Comentarii 0