Programare Competitivă

Căutarea binară

Am învățat deja să căutăm o valoare într-un vector parcurgând fiecare element, de la primul la ultimul. Aceasta se numește căutare liniară (sau secvențială).

Dar dacă vectorul este sortat, putem face mult mai bine.

Problema căutării

Avem un vector sortat crescător cu n elemente și un număr x. Vrem să aflăm dacă x se află în vector.

Exemplu:

Vector sortat: 2 5 8 12 16 23 38 42 56 72
Căutăm: x = 23

Căutarea liniară (recapitulare)

int gasit = 0;

for (int i = 1; i <= n; i++) {
    if (v[i] == x) {
        gasit = 1;
    }
}

Aceasta verifică fiecare element. Dacă vectorul are 1.000.000 de elemente, face 1.000.000 de comparații.

Putem face mai bine?

Ideea căutării binare

Gândește-te la cum cauți un cuvânt în dicționar:

  1. Nu începi de la prima pagină.
  2. Deschizi undeva la mijloc.
  3. Dacă cuvântul tău e înainte de pagina curentă, cauți în jumătatea stângă.
  4. Dacă e după, cauți în jumătatea dreaptă.
  5. Repeți până găsești cuvântul.

Căutarea binară face exact același lucru, dar cu un vector sortat.

Algoritmul pas cu pas

Avem un interval de căutare definit de doi indici: st (stânga) și dr (dreapta).

  1. Calculăm mijlocul: mij = (st + dr) / 2
  2. Comparăm v[mij] cu x:
    • Dacă v[mij] == x → am găsit!
    • Dacă v[mij] < x → x este în jumătatea dreaptă → st = mij + 1
    • Dacă v[mij] > x → x este în jumătatea stângă → dr = mij - 1
  3. Repetăm cât timp st <= dr
  4. Dacă am terminat fără să găsim → x nu există în vector

Exemplu detaliat

Vector: 2 5 8 12 16 23 38 42 56 72 (indexat de la 1 la 10)

Căutăm: x = 23

Pasul 1

st = 1,  dr = 10,  mij = (1 + 10) / 2 = 5

v[5] = 16

16 < 23  →  x este la dreapta  →  st = 6
      v[1]  v[2]  v[3]  v[4]  v[5]  v[6]  v[7]  v[8]  v[9]  v[10]
       2     5     8    12    [16]   23    38    42    56    72
                                ↑
                              mij=5
                              16 < 23 → mergem la dreapta

Pasul 2

st = 6,  dr = 10,  mij = (6 + 10) / 2 = 8

v[8] = 42

42 > 23  →  x este la stânga  →  dr = 7
                                v[6]  v[7]  v[8]  v[9]  v[10]
                                 23    38   [42]   56    72
                                              ↑
                                            mij=8
                                            42 > 23 → mergem la stânga

Pasul 3

st = 6,  dr = 7,  mij = (6 + 7) / 2 = 6

v[6] = 23

23 == 23  →  GĂSIT pe poziția 6!
                                v[6]  v[7]
                                [23]   38
                                  ↑
                                mij=6
                                23 == 23 → GĂSIT!

Rezumat

Pas st dr mij v[mij] Comparație Acțiune
1 1 10 5 16 16 < 23 st = 6
2 6 10 8 42 42 > 23 dr = 7
3 6 7 6 23 23 == 23 GĂSIT!

Am găsit 23 în doar 3 pași, nu 10!

Exemplu: valoare care NU există

Vector: 2 5 8 12 16 23 38 42 56 72

Căutăm: x = 15

Pas st dr mij v[mij] Comparație Acțiune
1 1 10 5 16 16 > 15 dr = 4
2 1 4 2 5 5 < 15 st = 3
3 3 4 3 8 8 < 15 st = 4
4 4 4 4 12 12 < 15 st = 5

Acum st = 5 > dr = 4 → nu mai avem unde căuta → 15 nu există în vector.

Am verificat în 4 pași, nu 10.

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int x;
    fin >> x;

    int st = 1, dr = n;
    int gasit = 0;
    int pozitie = -1;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (v[mij] == x) {
            gasit = 1;
            pozitie = mij;
            st = dr + 1; // ieșim din buclă
        } else if (v[mij] < x) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    if (gasit == 1) {
        fout << "DA, pe pozitia " << pozitie;
    } else {
        fout << "NU";
    }

    return 0;
}

date.in:

10
2 5 8 12 16 23 38 42 56 72
23

date.out:

DA, pe pozitia 6

De ce este rapidă?

La fiecare pas, înjumătățim intervalul de căutare.

Nr. elemente Căutare liniară (cel mai rău caz) Căutare binară (cel mai rău caz)
10 10 pași 4 pași
100 100 pași 7 pași
1.000 1.000 pași 10 pași
1.000.000 1.000.000 pași 20 pași
1.000.000.000 1.000.000.000 pași 30 pași

Un miliard de elemente - căutarea binară are nevoie de doar 30 de pași!

Formula: pentru n elemente, căutarea binară face cel mult log₂(n) pași. De exemplu, log₂(1.000.000) ≈ 20.

Condiția esențială

Căutarea binară funcționează DOAR pe vectori sortați.

Dacă vectorul nu este sortat, comparația cu mijlocul nu ne spune nimic despre unde se află valoarea - ar putea fi oriunde.

De aceea, de multe ori:

  1. Mai întâi sortăm vectorul.
  2. Apoi aplicăm căutarea binară.

Varianta simplificată (doar DA/NU)

Dacă vrem doar să știm dacă x există, fără poziția:

int st = 1, dr = n;
int gasit = 0;

while (st <= dr) {
    int mij = (st + dr) / 2;

    if (v[mij] == x) {
        gasit = 1;
        break;
    } else if (v[mij] < x) {
        st = mij + 1;
    } else {
        dr = mij - 1;
    }
}

if (gasit == 1) {
    fout << "DA";
} else {
    fout << "NU";
}

Exemplu aplicat: câte valori din al doilea șir se găsesc în primul?

Avem un vector sortat v cu n elemente și m întrebări: pentru fiecare valoare x, verificăm dacă există în v.

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, m;

int main()
{
    fin >> n;

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    fin >> m;

    int cnt = 0;

    for (int q = 1; q <= m; q++) {
        int x;
        fin >> x;

        // Căutare binară
        int st = 1, dr = n;
        int gasit = 0;

        while (st <= dr) {
            int mij = (st + dr) / 2;

            if (v[mij] == x) {
                gasit = 1;
                break;
            } else if (v[mij] < x) {
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }

        if (gasit == 1) {
            cnt++;
        }
    }

    fout << cnt;

    return 0;
}

date.in:

10
2 5 8 12 16 23 38 42 56 72
5
8 15 23 100 2

date.out:

3

Valorile 8, 23 și 2 se găsesc în vector. Valorile 15 și 100 nu.

De ce e important?

Fără căutare binară, pentru fiecare din cele m întrebări am parcurge tot vectorul → m × n operații.

Cu căutare binară, fiecare întrebare costă doar log₂(n) pași → m × log₂(n) operații.

Dacă n = 100.000 și m = 100.000: - Căutare liniară: 10.000.000.000 operații (prea lent!) - Căutare binară: 100.000 × 17 ≈ 1.700.000 operații (instantaneu!)

Vizualizare: cum se micșorează intervalul

Căutăm x = 38 în vectorul 2 5 8 12 16 23 38 42 56 72:

Pas 1:  [2  5  8  12  16  23  38  42  56  72]     mij=16, 16<38 → dreapta
                               ─────────────
Pas 2:                        [23  38  42  56  72]  mij=42, 42>38 → stânga
                               ───────
Pas 3:                        [23  38]              mij=23, 23<38 → dreapta
                                   ──
Pas 4:                            [38]              mij=38, 38==38 → GĂSIT!

Intervalul se înjumătățește la fiecare pas: 10 → 5 → 2 → 1.

Greșeli frecvente

1. Vectorul nu este sortat

Căutarea binară pe un vector nesortat dă rezultate greșite. Trebuie mereu sortat înainte.

2. Formula greșită pentru mijloc

// GREȘIT:
int mij = st + dr / 2; // dr / 2 se calculează mai întâi!

// CORECT:
int mij = (st + dr) / 2; // parantezele sunt esențiale

Fără paranteze, se împarte doar dr la 2, nu suma.

3. Actualizarea greșită a limitelor

// GREȘIT:
st = mij;     // poate cauza buclă infinită!
dr = mij;     // idem

// CORECT:
st = mij + 1; // excludem mijlocul, căutăm strict la dreapta
dr = mij - 1; // excludem mijlocul, căutăm strict la stânga

Dacă scriem st = mij sau dr = mij, s-ar putea ca mij să rămână mereu la aceeași valoare → buclă infinită.

4. Condiția st <= dr (nu st < dr)

// GREȘIT:
while (st < dr) { // ratează cazul st == dr !

// CORECT:
while (st <= dr) { // verifică și când rămâne un singur element

Când st == dr, mai avem un element de verificat. Dacă folosim <, îl ratăm.

5. Confuzia cu indexarea

Dacă indexezi de la 0, inițializarea este st = 0, dr = n - 1. Dacă indexezi de la 1, inițializarea este st = 1, dr = n.

Amestecarea celor două stiluri duce la erori.

Când folosim căutarea binară?

  • Avem un vector sortat (sau îl putem sorta).
  • Trebuie să verificăm rapid dacă o valoare există.
  • Avem multe căutări de făcut în același vector.
  • Trebuie să găsim prima/ultima apariție a unei valori.

Când NU folosim căutarea binară:

  • Vectorul nu este sortat și nu merită să îl sortăm.
  • Avem o singură căutare pe un vector mic.
  • Vectorul se modifică frecvent (inserări/ștergeri).

Ce să reții

  • Căutarea binară funcționează doar pe vectori sortați.
  • La fiecare pas, înjumătățim intervalul de căutare.
  • Este extraordinar de rapidă: 20 pași pentru 1.000.000 de elemente.
  • Formula: mij = (st + dr) / 2, cu paranteze.
  • Actualizăm cu st = mij + 1 sau dr = mij - 1 (niciodată st = mij).
  • Condiția buclei: while (st <= dr).
  • Este una dintre cele mai importante tehnici din informatică.

Probleme

pbinfoCautare Binara→

pbinfoTriunghiuri1→

pbinfoCb→

pbinfoColina→

Cuprins Inapoi Inainte