Căutarea binară este un algoritm eficient de căutare, folosit de obicei pentru a căuta o anumită valoare într-un vector sortat, de dimensiuni mari. În acest articol voi prezenta algoritmul de căutare binară, alternativele STL, căutarea binară pe funcții monotone, precum și o problemă interesantă ce folosește căutare binară.
Algoritmul de căutare secvențială
Se pune problema căutării unui număr x într-un vector v sortat crescător, indexat de la 0, de lungime n. Mai exact, trebuie să aflăm dacă x se găsește în vector, și în caz afirmativ, pe ce poziție se află acest număr (cea mai din stânga în caz că sunt mai multe). Dacă numărul nu-i aparține vectorului, se cere să se afișeze -1.
Soluția naivă constă într-o căutare secvențială, adică parcurgerea completă a vectorului. Folosim o variabilă pos pentru a reține poziția pe care se găsește x. Inițializăm această variabilă cu valoarea -1. La fiecare pas testăm dacă elementul curent este cel căutat. Dacă da, îi reținem poziția. La final, dacă pos încă are valoarea -1, înseamnă că x nu se află în vector. În caz contrar, în pos avem stocată ultima poziție la care s-a găsit numărul căutat.
|
1 2 3 4 5 |
pos = -1; for (i = 0; i < n; i++) if (v[i] == x) pos = i; cout << pos << '\n'; |
Putem optimiza un pic acest algoritm adăugând un break în cadrul if-ului, deoarece, dacă tocmai l-am găsit pe x, n-are sens să-l căutăm și în restul vectorului. În plus, procedând astfel, vom găsi cea mai din stânga poziție unde se află x. Totuși, în cel mai rău caz, programul face tot n iterații (pași), adică în cazul în care x se află pe ultima poziție din vector.
|
1 2 3 4 5 6 7 |
pos = -1; for (i = 0; i < n; i++) if (v[i] == x) { pos = i; break; } cout << pos << '\n'; |
Algoritmul de căutare binară
Vom face o analogie cu situația în care vrem să căutăm un anumit cuvânt într-un dicționar de hârtie. Dicționarul poate avea peste 1000 de pagini, așa că ar dura ore întregi să verificăm pe rând toate cuvintele. De aceea, avem nevoie de un algoritm mai bun. Soluția eficientă este să deschidem dicționarul la mijloc (cât de cât), și să ne uităm la un cuvânt de pe pagina respectivă. Dacă am găsit un cuvânt mai mic din punct de vedere alfabetic decât cel căutat, atunci cu siguranță toate cuvintele scrise înaintea lui sunt și ele mai mici decât cel căutat. Din acest motiv, n-are sens să ne continuăm căutarea în stânga, ci doar în dreapta. Apoi, deschidem dicționarul la jumătatea noului interval și repetăm procedeul până când găsim cuvântul căutat. Pe această idee se bazează și căutarea binară: La fiecare pas înjumătățim intervalul de căutare. De aici îi vine și numele.
Implementare în C++
Pentru implementarea căutării binare în C++, vom folosi două variabile pentru a reține capetele intervalului (deschis) curent de căutare: st și dr. Le vom inițializa cu -1 și respectiv n. Apoi, folosim un while în care testăm la fiecare pas dacă intervalul de căutare are lungimea cel puțin 1. Dacă nu, înseamnă că nu am găsit numărul, și se poate ieși din while.
În interiorul structurii repetitive calculăm mijlocul intervalului, folosind o variabilă m, urmând să comparăm elementul v[m] cu x în vederea actualizării intervalului. Dacă v[m] < x, continuăm căutarea în dreapta, deci st devine m. Altfel, continuăm căutarea în stânga, așa că dr devine m. Pe a doua ramură mergem chiar dacă v[m] == x, de aceea algoritmul returnează cea mai din stânga apariție a lui x. Dacă avem de căutat cea mai din dreapta apariție a lui x, nu trebuie decât să schimbăm ordinea în care testăm relația dintre v[m] și x (întâi punem >).
După ieșirea din while, trebuie să verificăm dacă dr nu a depășit poziția maximă (în cazul în care x este mai mare decât ultimul element din vector), și dacă v[dr] este egal cu x (pentru a ne asigura că x chiar se găsește pe poziția unde ne-am oprit).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
int m, st = -1, dr = n; while (dr - st > 1) { m = (st + dr) / 2; if (v[m] < x) st = m; else dr = m; } if (dr < n && v[dr] == x) cout << dr << '\n'; else cout << "-1\n"; |
Căutarea binară este unul dintre algoritmii simpli dar la implementarea căruia se greșește cel mai frecvent. De multe ori are bug-uri pentru cazurile particulare: x apare de mai multe ori, x e mai mic decât prima valoare din vector, x e mai mare decât ultima valoare din vector, etc. „Optimizarea” if (v[m] == x) break; nu face decât să complice codul, mai ales că numărul de pași pe care îi face algoritmul este oricum extrem de mic. Varianta prezentată de mine mi se pare cea mai clară implementare a căutării binare, deoarece se bazează pe invariantul (condiția adevărată de fiecare dată când se intră în while) v[st] < x <= v[dr] (considerăm v[-1] = -∞ și v[n] = +∞).
Dacă vectorul era indexat de la 1, st ar fi fost inițializat cu 0, iar dr cu n + 1. Ideea e ca st să fie cu 1 mai mic decât începutul intervalului închis pe care îl indică de fapt, iar dr cu 1 mai mare decât sfârșitul acestuia.
Exemple
Iată cum funcționează căutarea binară pe următoarele trei exemple. Am marcat cu albastru st, cu roșu dr, iar cu verde m.
Complexitatea căutării binare
Numărul de pași efectuați de algoritmul de căutare binară, adică de câte ori se intră în while, este egal cu numărul de împărțiri la 2 (la fiecare pas înjumătățim intervalul) necesare pentru a ajunge la un interval de lungime 0. Acest număr nu este fix, deoarece uneori prin împărțirea la 2 se obține restul 1 (vezi diferența dintre exemplele 2 și 3 de mai sus), dar este aproximativ $[\log_2 n]$. Așadar, complexitatea căutării binare este $O(\log_2 n)$.
Pentru a vedea cât de eficientă este căutarea binară, gândiți-vă că pe un vector de un miliard de elemente, căutarea binară face doar 30 de pași! Căutarea secvențială ar fi făcut 1 miliard, ceea ce durează mai bine de o secundă. Iar un motor de căutare ca Google face astfel de căutări tot timpul.
Alternative STL pentru căutarea binară
În biblioteca algorithm sunt definite patru funcții STL ce țin de căutarea binară. Acestea funcționează atât pe vectori statici, cât și pe vectori din STL, exact ca sort-ul.
binary_search
Funcția binary_search returnează printr-o valoare booleană doar dacă numărul căutat se găsește în vector, nu și poziția sa.
|
1 2 |
int v[] = {2, 7, 13, 13, 54, 86, 99, 437}; cout << binary_search(v, v + 7, 90) << '\n'; // 0 |
lower_bound și upper_bound
Funcția lower_bound returnează prima poziție unde se găsește numărul căutat în vector. Funcția upper_bound returnează poziția cu 1 mai mare decât ultima pe care se găsește numărul căutat. De fapt, este vorba de niște pointeri, nu poziții, în fine. Dacă numărul nu se găsește în vector, ambele funcții returnează poziția primului număr mai mare strict decât cel căutat. Sau v.end(), dacă toate numerele din vector sunt mai mici.
|
1 2 3 |
vector<int> v = {2, 7, 13, 13, 54, 86, 99, 437}; cout << lower_bound(v.begin(), v.end(), 13) - v.begin() << '\n'; // 2 cout << upper_bound(v.begin(), v.end(), 13) - v.begin() << '\n'; // 4 |
Aplicație la căutarea binară: Problema Ecuatii de pe InfoArena
Problema Ecuatii de pe InfoArena s-a dat în 2002 la ONI și e aproape identică cu una dată anul acesta la OJI, la clasa a 10-a. Este o problemă de căutare binară cu o idee foarte interesantă, ce folosește o tehnică cunoscută în literatura de specialitate drept meet in the middle. Pentru o ecuație de gradul 3 cu 5 necunoscute, dată prin coeficienți, trebuie să-i determinăm numărul de soluții.
Pentru că intervalul de valori al soluțiilor este foarte mic, punem într-un vector toate combinațiile de forma $a \cdot x_{1}^{3} + b \cdot x_{2}^{3} + c \cdot x_{3}^{3}$, iar apoi îl sortăm. După aceea, calculăm toate combinațiile de forma $d \cdot x_{4}^{3} + e \cdot x_{5}^{3}$, iar pentru fiecare, căutăm binar de câte ori apare valoarea complementară (diferența până la 0) a lor în vectorul sum, și adunăm acest număr la soluție. Se poate folosi un tabel de hashing pentru găsirea mai rapidă a valorilor complementare, însă nu este obligatoriu. Iată o sursă C++ foarte simplă de 100 de puncte:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <vector> #include <fstream> #include <algorithm> #define SMAX 110 #define int64 long long int using std::sort; using std::vector; using std::lower_bound; using std::upper_bound; std::ifstream fin("eqs.in"); std::ofstream fout("eqs.out"); int sol; int64 pows[SMAX]; #define pows (pows + 50) int64 a, b, c, d, e, f; vector<int64> sum; int main() { for (int i = -50; i <= 50; i++) pows[i] = i * i * i; fin >> a >> b >> c >> d >> e; for (int s1 = -50; s1 <= 50; s1++) if (s1) for (int s2 = -50; s2 <= 50; s2++) if (s2) for (int s3 = -50; s3 <= 50; s3++) if (s3) sum.push_back(a * pows[s1] + b * pows[s2] + c * pows[s3]); sort(sum.begin(), sum.end()); for (int s4 = -50; s4 <= 50; s4++) if (s4) for (int s5 = -50; s5 <= 50; s5++) if (s5) { int64 toFind = -d * pows[s4] - e * pows[s5]; sol += upper_bound(sum.begin(), sum.end(), toFind) - lower_bound(sum.begin(), sum.end(), toFind); } fout << sol << '\n'; fout.close(); return 0; } |
Căutarea binară pe funcții monotone
Putem folosi căutarea binară și pe funcții monotone! O funcție monotonă este o funcție care, pentru domeniul său de definiție, păstrează sau inversează ordinea elementelor. Pentru o anumită valoare $y$, putem căuta binar numărul $x$ pentru care $f(x)=y$. La fel de bine, putem face și opusul, adică pentru un $x$ să căutăm $y$ astfel încât $f(x)=y$.
De exemplu, funcția radical este o funcție crescătoare. Să zicem că vrem să calculăm radicalul de ordin k al lui n, cu o precizie de două zecimale. Iată cum arată o căutare binară care rezolvă această problemă (funcția pow(a, b) returnează ab):
|
1 2 3 4 5 6 7 8 9 |
double m, st = 0, dr = n + 0.01; while (dr - st > 0.01) { m = (st + dr) / 2; if (pow(m, k) > n) dr = m; else st = m; } cout << dr << '\n'; |
La concursuri, când căutăm numere într-un vector, clar nu putem avea intervalul de lungime un miliard, însă la căutarea binară pe funcții este posibil. Așadar, trebuie să fim atenți că la pasul în care se calculează (st + dr) / 2, e posibil ca suma să depășească valoarea maximă suportată de tipul de date al a și b. Putem evita această problemă calculând mijlocul astfel: st + (dr - st) / 2.
Uneori, funcțiile monotone pe care se pot efectua căutări binare sunt mult mai complexe, iar tehnica în care se face căutare pe astfel de funcții se numește căutare binară pe rezultat. Dacă folosind mijlocul intervalului putem construi o soluție ce respectă condițiile problemei, continuăm căutarea într-o jumătate a intervalului pentru o soluție mai bună. Dacă nu, continuăm căutarea în jumătatea cealaltă. Câteva probleme ce se bazează pe această idee sunt rover, checkin și uscat.
Bonus: Căutare binară folosind operații pe biți
Căutarea binară poate fi implementată și folosind operații pe biți, și nu mă refer la faptul că pur și simplu înlocuim / 2 cu >> 1. Algoritmul folosește o abordare mai degrabă greedy decât divide et impera, dar deși are complexitatea căutării binare obișnuite, în practică funcționează de 4 ori mai repede!
Se calculează cea mai mică putere p a lui 2 mai mare sau egală cu n. La indexul i se adună valoarea curentă a puterii dacă pe v[i + p] se află o valoare mai mică sau egală cu x. Apoi, se înjumătățește puterea și se repetă procedeul. Acest program returnează ultima apariție a lui x în vector.
|
1 2 3 4 5 6 7 8 9 10 11 |
int i, p; for (p = 1; p < n; p <<= 1); for (i = 0; p; p >>= 1) if (i + p < n && v[i + p] <= x) i += p; if (v[i] == x) cout << i << ' '; else cout << "-1\n"; |
Dacă aveți vreo întrebare legată de căutarea binară, nu ezitați să o adresați mai jos. Vă voi răspunde cât de repede se poate 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!
ce înseamnă #define pows (pows + 50) ?
Acel
#defineînseamnă că atunci când vei scriepows[x], acesta va fi văzut drept(pows + 50)[x], care este tot una cupows[x + 50]. Astfel, elementele vectorului vor fi decalate cu50de poziții la dreapta. Am făcut asta ca să pot accesa poziții „negative” din vector fără să scriu peste tot acel+ 50.