Căutarea binară în C++ – Află secretele căutării binare!

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 dreapta în caz că există 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. 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 zile întregi să verificăm pe rând fiecare cuvânt. 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 x cu v[md] în vederea actualizării intervalului. Dacă x < v[md], continuăm căutarea în stânga, deci hi devine md. Altfel, continuăm căutarea în dreapta, așa că lo devine md. Pe a doua ramură mergem chiar dacă x == v[md], de aceea algoritmul returnează cea mai din dreapta apariție a lui x. Dacă avem de căutat cea mai din stânga apariție a lui x, nu trebuie decât să schimbăm ordinea în care testăm relația dintre x și v[md] (întâi punem cazul în care x > v[md]).

După ieșirea din while, trebuie să verificăm dacă lo a ieșit din vector (dacă lo a devenit -1). În acest caz, x este mai mic decât primul element din vector. În caz contrar, dacă în plus avem că v[lo] este egal cu x, înseamnă că cea mai din dreapta poziție pe care se află x este lo.

int lo = -1, hi = n;
while (hi - lo > 1) {
    int md = (lo + hi) / 2;
    if (x < v[md])
        hi = md;
    else
        lo = md;
}
if (lo > -1 && v[lo] == x)
    cout << lo << '\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] = -INF și v[n] = +INF). De ce? Păi, inițial avem -INF < x < +INF. Apoi, la fiecare dintre ceilalți pași, știm din if că hi a fost actualizat doar dacă x < v[hi], iar lo doar dacă s-a intrat pe ramura else, deci dacă x >= v[lo].

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ă o animație care sigur va clarifica lucrurile! Aceasta tratează cinci cazuri, cât mai diverse:

• x apare o singură dată în vector
• x apare de mai multe ori în vector
• x este mai mare decât ultimul element din vector
• x este mai mic decât primul element din vector
• x nu se află în nicio situație de mai sus

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$ 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ă dacă numărul căutat se găsește în vector, dar 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 Ecuații de pe InfoArena

Problema Ecuații 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';
    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 pwr(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 (pwr(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, lungimea intervalului clar nu poate fi un miliard, însă la căutarea binară pe funcții aceasta poate fi și $10^{18}$ 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 long long int. 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! La noi, această tehnică poartă numele de Căutarea binară a lui Pătrașcu.

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 din 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 << '\n';
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