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, căutarea binară folosind operații pe biți, precum și o aplicație interesantă ce folosește tehnica meet in the middle.
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.
int pos = -1;
for (int 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), asta în cazul în care x
se află pe ultima poziție din vector.
int pos = -1;
for (int 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 lexicografic 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: lo
și hi
(nu-mi plac 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ă md
, urmând să comparăm elementul v[md]
cu x
în vederea actualizării intervalului. Dacă v[md] < x
, continuăm căutarea în dreapta, deci lo
devine md
. Altfel, continuăm căutarea în stânga, așa că hi
devine md
. Pe a doua ramură mergem chiar dacă v[md] == 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[md]
și x
(întâi punem cazul în care v[md] > x
).
După ieșirea din while
, trebuie să verificăm dacă hi
nu a depășit poziția maximă (în cazul în care x
este mai mare decât ultimul element din vector), și dacă v[hi]
este egal cu x
(pentru a ne asigura că x
chiar se găsește pe poziția unde ne-am oprit).
int lo = -1, hi = n;
while (hi - lo > 1) {
int md = (lo + hi) / 2;
if (v[md] < x)
lo = md;
else
hi = md;
}
if (hi < n && v[hi] == x)
cout << hi << '\n';
else
cout << "-1\n";
Căutarea binară este unul dintre algoritmii simpli dar la implementarea căruia se greșește 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[md] == 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[lo] < x <= v[hi]
(considerăm că v[-1] = -∞
și v[n] = +∞
).
Dacă vectorul era indexat de la 1
, lo
ar fi fost inițializat cu 0
, iar hi
cu n + 1
. Ideea e ca lo
să fie cu 1
mai mic decât începutul intervalului închis pe care îl indică de fapt, iar hi
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 lo
, cu roșu hi
, iar cu verde md
.
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 n)$.
Pentru a înțelege 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.
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.
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 rădăcinilor 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:
#include <bits/stdc++.h>
using namespace std;
ifstream fin("eqs.in");
ofstream fout("eqs.out");
int sol;
int64_t pows[101];
#define pows (pows + 50)
int64_t a, b, c, d, e, f;
vector<int64_t> 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_t 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ă $a^b$):
double lo = -0.01, hi = max(n, 1) + 0.01;
while (hi - lo > 0.01) {
double md = (lo + hi) / 2;
if (pow(md, k) > n)
hi = md;
else
lo = md;
}
cout << hi << '\n';
Capătul din dreapta al intervalului l-am setat la $\max(n, 1)$ pentru a nu returna un răspuns greșit în cazul în care $n \lt 1$. Atunci când $n$ este subunitar, radicalul său este mai mare decât el însuși, așa că ar trebui să-l căutăm în intervalul $[0, 1]$, nu în $[0, 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ă (lo + hi) / 2
, s-ar putea ca suma să depășească valoarea maximă suportată de tipul de date al a
și b
. Putem evita această problemă calculând mijlocul astfel: lo + (hi - lo) / 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ă. Două probleme ce se bazează pe această idee sunt Rover și Checkin.
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.
int p;
for (p = 1; p < n; p <<= 1);
int i;
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
Bună ziua,
Nu înțeleg un mecanism… El e bun, eu nu înțeleg…
Perfect… Am intrat în
while
… Calculezmd
… Perfect… Ce se întâmplă dacă chiarv[md] == x
? Nu intru înif
pentru căv[md]
nu estex
… Ce se întâmplă, atunci? Cum se iese dinwhile
?!…Ceva nu pricep eu?!
Sper să nu râdeți de mine…
Cu stimă,
Cristian
Nu apare corect ce am zis…
Ideea este că nu intru în
if
și nici înelse
…Cum ies din
while
atunci…?Cristian
Revin…
Adică din
while (hi - lo > 1)
nu ies decât atunci când efectivhi
șilo
sunt pe poziții consecutive sau egale… Asta înțeleg eu din acestwhile
… Indiferent dacă pe parcursv[md]
este egal cux
… Afirmație…Cu stimă,
Cristian
Dacă nu intri în
if
e clar că intri înelse
. Dinwhile
ieși doar cândlo
șihi
se află pe poziții consecutive. Nu pot ajunge niciodată să fie egale. Am în articol o poză cu 3 exemple de căutare binară. Dacă nu sunt suficiente, mai dă-ți tu exemple și vezi pe hârtie pas cu pas cum se execută codul. Sau dacă ți-e lene, fă un program care afișează la fiecare pas dinwhile
valorilelo
,md
șihi
. Ia în considerare cazurile când numărul căutat se află în vector, când nu se află, când e mai mic decât primul număr, când e mai mare decât ultimul etc.Din ce scrieți dvs înțeleg următoarele:
1. Din
while
ies cândlo
șihi
ajung pe poziții consecutive…while
merge până la final…2. Dacă nu intru în
if
, intru înelse
care ia în calcul două situații: a)v[m] > x
și b)v[m] == x
.3. După ce ies din
while
verific situația cuif
scris mai jos: Din verificare ori aflu poziția valorii găsite în vector (și care estehi
), ori poziția-1
adică valoarea nu este în vector…Așa este cum am descris eu?
Mulțumesc frumos pentru răspuns.
Cu stimă,
Cristian
Da, corect!
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 cu50
de 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
.