Căutarea binară

Căutarea binară funcționează pe un tablou sortat. Comparăm valoarea căutată cu elementul din mijloc și păstrăm numai jumătatea în care mai poate apărea. În $[2,4,7,9,12]$, căutarea lui 9 vede mai întâi 7 la indicele 2, apoi restrânge intervalul la indicii 3–4 și găsește 9.

Căutarea binară funcționează numai pe un tablou sortat. Se păstrează un interval de căutare [st, dr], inițial tot tabloul. La fiecare pas se alege elementul din mijloc, mij = st + (dr - st) / 2, și se compară cu valoarea căutată $x$: dacă v[mij] == x, căutarea s-a terminat; dacă v[mij] < x, valoarea poate fi doar în dreapta, deci st = mij + 1; altfel poate fi doar în stânga, deci dr = mij - 1. Dacă intervalul devine gol (st > dr), valoarea lipsește. Intervalul se înjumătățește la fiecare pas, deci numărul de pași este cel mult $[{\log }_{2}n]+1$: pentru $n=1000$ sunt cel mult 10 pași, iar pentru $n=10^9$ cel mult 30. Expresia st + (dr - st) / 2 evită depășirea tipului pe care ar putea-o produce (st + dr) / 2 la valori mari.

Exemplul 1 — valoare găsită. În tabloul $2,4,7,9,12$ se caută $x=9$.

#include <iostream>
using namespace std;
int main() {
    int v[] = {2, 4, 7, 9, 12};
    int st = 0, dr = 4, x = 9, poz = -1;
    while (st <= dr) {
        int mij = st + (dr - st) / 2;
        if (v[mij] == x) { poz = mij; break; }
        if (v[mij] < x) st = mij + 1;
        else dr = mij - 1;
    }
    cout << poz;
    return 0;
}

Primul mijloc este 2, cu valoarea 7, mai mică decât 9, deci st devine 3. Al doilea mijloc este $3+(4-3)/2=3$, cu valoarea 9: găsit. Se afișează 3, după două comparații cu elementele tabloului.

Exemplul 2 — valoare absentă. Se caută $x=6$ în același tablou.

1. st = 0, dr = 4, mij = 2: $7>6$, deci dr = 1.
2. st = 0, dr = 1, mij = 0: $2<6$, deci st = 1.
3. st = 1, dr = 1, mij = 1: $4<6$, deci st = 2.
4. st = 2 este mai mare decât dr = 1, intervalul este gol și ciclul se oprește.

Poziția rămâne $-1$. S-au făcut trei comparații pentru cinci elemente, față de cinci comparații la căutarea secvențială.

Exemplul 3 — valori repetate. În tabloul sortat $1,3,3,3,5$ căutarea lui 3 găsește primul mijloc, indicele 2, care este una dintre aparițiile valorii, nu neapărat prima. Pentru prima apariție, după ce găsești v[mij] == x memorezi poz = mij și continui în stânga cu dr = mij - 1; algoritmul ajunge la indicele 1. Pentru ultima apariție continui în dreapta cu st = mij + 1; se obține 3.

Exemplul 4 — prima poziție care nu este mai mică decât $x$. O variantă păstrează intervalul [st, dr), cu dr exclus, inițial st = 0 și dr = n. Ciclul while (st < dr) calculează mij = st + (dr - st) / 2 și face st = mij + 1 dacă v[mij] < x, altfel dr = mij. Invariantul este că toate elementele dinaintea lui st sunt mai mici decât $x$, iar cele de la dr încolo sunt mai mari sau egale cu $x$. La final st este numărul elementelor mai mici decât $x$. Pentru $2,4,7,9,12$ și $x=6$: mij = 2 (valoarea 7 nu este mai mică) face dr = 2; apoi mij = 1 (valoarea 4 este mai mică) face st = 2, iar rezultatul 2 este poziția în care s-ar insera 6. În $1,3,3,3,5$ se obține 1 pentru $x=3$ (prima apariție) și 4 pentru $x=4$. Dacă $x$ este mai mare decât toate elementele, rezultatul este $n$.

Numărul de pași și precondiția. Numărul maxim de pași este $[{\log }_{2}n]+1$: 3 pentru $n=7$, 10 pentru $n=1000$ și 20 pentru $n=10^6$. Precondiția sortării nu este opțională. În tabloul nesortat $4,2,9,1$ căutarea lui 2 reușește din întâmplare (mijlocul este chiar elementul 2), dar căutarea lui 1 întoarce $-1$, deși 1 este pe poziția 3: la primul pas $2>1$ și algoritmul renunță la jumătatea din dreapta, unde se afla valoarea.

Verifică precondiția sortării și sensul ei. Pentru date descrescătoare, ramurile de actualizare trebuie inversate. Codul din primul exemplu întoarce o apariție, nu neapărat prima dintre duplicate. Atenție la limitele intervalului: st <= dr în condiția ciclului acoperă cazul intervalului cu un singur element, iar actualizările mij + 1 și mij - 1 garantează că intervalul se micșorează; dacă s-ar scrie st = mij, ciclul ar putea să nu se mai termine. Când enunțul cere numărul de pași, urmărește valorile st, dr și mij în tabel.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int v[] = {2, 4, 7, 9, 12, 15, 20};
int st = 0, dr = 6, x = 15, poz = -1, pasi = 0;
while (st <= dr) {
    int mij = (st + dr) / 2;
    pasi++;
    if (v[mij] == x) { poz = mij; break; }
    if (v[mij] < x) st = mij + 1;
    else dr = mij - 1;
}
cout << poz << ' ' << pasi;

• a) 5 2
• b) 5 3
• c) 4 2
• d) -1 3

Ideea. Compari $x$ cu elementul din mijloc. Dacă sunt egale, ai terminat. Dacă $x$ este mai mic, toate elementele din dreapta mijlocului sunt și ele mai mari decât $x$, deci îl cauți doar în stânga; dacă $x$ este mai mare, doar în dreapta. Zona în care poate fi $x$ se înjumătățește la fiecare pas, până când îl găsești sau zona devine goală. Cu pozițiile $1\dots n$ și zona $[st,dr]$, algoritmul este, în pseudocod:

citește n, v[1], …, v[n] (sortat crescător), x
st ← 1; dr ← n; poz ← 0
┌cât timp st ≤ dr și poz = 0 execută
│  m ← [(st + dr) / 2]
│ ┌dacă v[m] = x atunci
│ │  poz ← m
│ │altfel
│ │ ┌dacă x < v[m] atunci dr ← m - 1
│ │ │altfel st ← m + 1
│ │ └■
│ └■
└■
scrie poz

De ce e atât de rapidă. După $k$ comparații, zona de căutare are cel mult $n/2^k$ elemente. Ea rămâne nevidă doar cât timp $2^k\le n$, deci se fac cel mult $\lfloor {\log }_{2}n\rfloor +1$ comparații. Pentru un milion de elemente înseamnă 20 de comparații, față de un milion la căutarea secvențială. Metoda este un caz particular de divide et impera, în care se continuă într-o singură jumătate.

Variante utile. Aceeași idee găsește și alte poziții, dacă schimbi ce faci la egalitate: prima poziție cu v[i] >= x (unde ar trebui inserat $x$ ca vectorul să rămână sortat), prima poziție cu o valoare egală cu $x$ când sunt mai multe egale, sau numărul de apariții ale lui $x$. Căutarea binară se aplică și pe valorile unei funcții crescătoare, de exemplu ca să afli cel mai mare număr natural $r$ cu $r\cdot r\le n$.

Același tablou arată și numărul de pași în alte cazuri. Pentru $x=20$ mijloacele sunt 3, 5 și 6, deci valoarea se găsește după 3 pași, pe poziția 6. Pentru $x=1$ și pentru $x=13$, valori care lipsesc, secvența face tot 3 pași și afișează -1 3. Cu 7 elemente nu se poate depăși $[{\log }_{2}7]+1=3$ pași, indiferent dacă valoarea există sau nu. Un răspuns care indică 4 pași pentru acest tablou arată că s-a numărat greșit, de exemplu s-a reluat un interval deja eliminat.

Exemple rezolvate

Exemplul 1: urmărirea pașilor. În vectorul 3, 8, 15, 21, 27, 34, 42, 50, 61 caută 42, apoi 10.

1. Pentru 42: st = 1, dr = 9, m = 5, v[5] = 27 < 42, deci st = 6; m = 7, v[7] = 42: găsit pe poziția 7, după 2 comparații.
2. Pentru 10: m = 5, v[5] = 27 > 10, deci dr = 4; m = 2, v[2] = 8 < 10, deci st = 3; m = 3, v[3] = 15 > 10, deci dr = 2. Acum st > dr: 10 nu există. Au fost comparate cu $x$ valorile 27, 8, 15.

#include <iostream>
using namespace std;

int v[] = {0, 3, 8, 15, 21, 27, 34, 42, 50, 61}, n = 9;

int cauta(int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        int m = (st + dr) / 2;
        cout << v[m] << " ";          // elementul comparat cu x
        if (v[m] == x)
            return m;
        if (x < v[m])
            dr = m - 1;
        else
            st = m + 1;
    }
    return 0;
}

int main() {
    int p = cauta(42);
    cout << "-> " << p << "\n";
    p = cauta(10);
    cout << "-> " << p << "\n";
    return 0;
}

Programul afișează, pentru fiecare căutare, elementele comparate și poziția găsită (0 dacă lipsește):

27 42 -> 7
27 8 15 -> 0

Exemplul 2: numărul maxim de comparații. Care este numărul maxim de elemente comparate cu $x$ la căutarea binară într-un vector sortat cu 100 de elemente? Dar cu 1000?

1. După fiecare comparație fără succes, zona rămasă are cel mult jumătate din elemente: 100, 50, 25, 12, 6, 3, 1. Sunt 7 zone nevide, deci cel mult 7 comparații.
2. Pentru 1000: $2^9=512\le 1000<1024=2^{10}$, deci cel mult $9+1=10$ comparații.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;                         // vectorul este 1, 2, ..., n
    int maxim = 0;
    for (int x = 0; x <= n; x++)      // x = 0 lipseste; celelalte exista
        for (int t = 0; t < 2; t++) {
            int st = 1, dr = n, nr = 0;
            double cautat = x + 0.5 * t;   // si valori dintre elemente
            while (st <= dr) {
                int m = (st + dr) / 2;
                nr++;
                if (m == cautat) break;
                if (cautat < m) dr = m - 1;
                else st = m + 1;
            }
            if (nr > maxim) maxim = nr;
        }
    cout << maxim << "\n";
    return 0;
}

Programul încearcă toate valorile din vector și toate valorile aflate între ele. Pentru intrarea 100, afișează:

7

Pentru 1000 afișează 10.

Exemplul 3: prima apariție și numărul de apariții. În vectorul sortat 2, 4, 4, 4, 7, 9, câte apariții are valoarea 4?

1. Prima poziție cu v[i] >= 4 este 2; prima poziție cu v[i] > 4 este 5.
2. Numărul de apariții este $5-2=3$.
3. Funcția caută prima poziție i cu v[i] >= x: dacă v[m] >= x, răspunsul este m sau la stânga lui, deci reții m și continui în stânga.

#include <iostream>
using namespace std;

int v[] = {0, 2, 4, 4, 4, 7, 9}, n = 6;

int primaPoz(int x) {                 // prima pozitie cu v[i] >= x, sau n + 1
    int st = 1, dr = n, rez = n + 1;
    while (st <= dr) {
        int m = (st + dr) / 2;
        if (v[m] >= x) {
            rez = m;
            dr = m - 1;
        } else
            st = m + 1;
    }
    return rez;
}

int main() {
    cout << primaPoz(4) << " " << primaPoz(5) - primaPoz(4) << " " << primaPoz(10) << "\n";
    return 0;
}

Programul afișează prima poziție a lui 4, numărul aparițiilor lui și poziția la care s-ar insera 10:

2 3 7

Exemplul 4: partea întreagă a radicalului. Se citește un număr natural $n\le 1000000000$. Află cel mai mare număr natural $r$ cu $r\cdot r\le n$, fără funcția sqrt. Pentru $n=2026$, $r=45$, pentru că $45\cdot 45=2025\le 2026<2116=46\cdot 46$.

1. Funcția $r\cdot r$ este crescătoare, deci cauți binar pe valorile lui $r$, între 0 și $n$.
2. Dacă $m\cdot m\le n$, $m$ este un candidat și poate exista unul mai mare: reții $m$ și cauți în dreapta. Altfel cauți în stânga.

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long st = 0, dr = n, r = 0;
    while (st <= dr) {
        long long m = (st + dr) / 2;
        if (m * m <= n) {
            r = m;
            st = m + 1;
        } else
            dr = m - 1;
    }
    cout << r << "\n";
    return 0;
}

Pentru intrarea 2026, programul afișează:

45

Variabilele sunt long long, pentru că m * m depășește tipul int: pentru $n=1000000000$, primul mijloc este 500 000 000, iar pătratul lui are 18 cifre.

Exemplul 5: nivel de examen, valorile comparate. Un vector sortat are 15 elemente, valorile 10, 20, 30, …, 150. Care sunt valorile cu care este comparat $x=125$ și câte comparații se fac?

1. m = 8, v[8] = 80 < 125, deci st = 9.
2. m = 12, v[12] = 120 < 125, deci st = 13.
3. m = 14, v[14] = 140 > 125, deci dr = 13.
4. m = 13, v[13] = 130 > 125, deci dr = 12 < st. Valoarea nu există.
5. Valorile comparate: 80, 120, 140, 130, adică 4 comparații, numărul maxim pentru 15 elemente ($15=2^4-1$).

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen cuprinde „Metode de căutare (secvențială, binară)” și analiza complexității unui algoritm, la algoritmii elementari (anexa 2 la OMECTS 4800/2010). Formatul probei și subiectele din 2026 sunt pe pagina subiectelor și baremelor Bac 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.

Pe programa școlară veche, căutarea secvențială și căutarea binară sunt la clasa a X-a, la algoritmii de prelucrare a tablourilor (OMECI 5099/2009); pe programa nouă, ea este la clasa a X-a, din 2027–2028, la metodele de prelucrare a listelor sortate (OMEC 4370/2026).

Greșeli frecvente

• Greșit: căutarea binară merge pe orice tablou.
  Corect: tabloul trebuie sortat în sensul presupus de algoritm.
• Greșit: la v[mij] < x se actualizează dr.
  Corect: valoarea poate fi doar în dreapta, deci st = mij + 1.
• Greșit: la valori repetate, căutarea binară găsește mereu prima apariție.
  Corect: găsește o apariție; pentru prima se continuă în stânga.
• Greșit: căutarea binară funcționează la fel pe orice ordine a datelor.
  Corect: cere un tablou sortat conform comparațiilor folosite; pe un vector nesortat dă rezultate greșite, deci îl sortezi întâi sau cauți secvențial.
• Greșit: după v[mij] < x păstrăm jumătatea stângă.
  Corect: păstrăm partea dreaptă.
• Greșit: găsirea unei apariții garantează că este prima.
  Corect: duplicatele cer o variantă specială, ca în exemplul 3.
• Greșit: condiția buclei poate fi st < dr.
  Corect: cu st < dr, zona cu un singur element nu mai este verificată, iar o valoare aflată acolo nu este găsită; condiția este st <= dr.
• Greșit: actualizările pot fi dr = m sau st = m.
  Corect: se folosesc m - 1 și m + 1; altfel bucla poate să nu se mai termine, când st și dr sunt vecine.
• Greșit: (st + dr) / 2 este mereu sigur.
  Corect: pentru indici foarte mari, st + dr poate depăși tipul int; forma st + (dr - st) / 2 evită depășirea.

Înainte și după

Întrebări frecvente