Căutare binară în C++

În multe situații avem un șir de elemente (cum ar fi numere naturale) și suntem nevoiți să verificăm dacă o anumită valoare se găsește sau nu în șir (și eventual să găsim și poziția pe care se află).

Un algoritm clasic parcurge elementele de la început la final și compară valoarea de căutat cu fiecare element în parte, pe rând. Acesta este un algoritm brut și ineficient, în special pentru un număr mare de elemente, complexitatea sa fiind O(n).

Pentru un șir de valori ordonate crescător, putem să ne folosim de un algoritm de căutare binară, care reușește să răspundă la întrebarea propusă în doar O(log2 n), un timp mult mai bun.

Cum funcționează algoritmul căutarea binară?

Algoritmul de căutare binară ia șirul (să îl numim a, cu elementele pe pozițiile de la 1 la n) cu valori ordonate (de obicei crescător) și valoarea căutată, x. Începe prin a compara elementul din mijlocul șirului lui a cu x. Există trei situații posibile:

1. Valoarea din mijloc, a[mij], este chiar egală cu x. În acest caz ne oprim și marcăm că am găsit elementul;
2. Valoarea din mijloc, a[mij], este mai mică decât x. Atunci, deoarece șirul este sortat crescător, nu are rost să mai verificăm elementele din stânga lui a[mij] (cu pozițiile de la 1 la mij - 1), căci categoric x este mai mare decât toate acestea. Așadar considerăm doar elementele șirului de pe pozițiile mij + 1 până la n și repetăm algoritmul pe această jumătate, luând mijlocul acestei secvențe;
3. Valoarea din mijloc, a[mij], este mai mare decât x. Atunci, similar ca la al doilea caz, nu are rost să verificăm elementele din dreapta lui a[mij], așadar am redus șirul la jumătate.

Dacă, la final, am ajuns pe o poziție a cărei valoare diferă de x, atunci x cu siguranță nu se găsește în șir.

Vedem că algoritmul acesta este mult mai eficient, întrucât la fiecare pas împărțim șirul în două, reducând semnificativ numărul de elemente de comparat.

Exemplu vizual: căutare binară

Să luăm următorul șir, unde căutăm valoarea x = 35.

Luăm poziția din mijloc: (1 + 7) / 2 = 4. Comparăm valoarea sa, 37, cu x = 35. Vedem că este mai mare, așadar nu ne mai interesează elementele din dreapta acestui element (le marcăm cu roșu).

Din partea rămasă a șirului (elementele de pe pozițiile de la 1 la 3), luăm mijlocul, (1 + 3) / 2 = 2. Cum 23 este mai mic decât 35, tăiem elementele de pe pozițiile 1 și 2.

Am rămas cu elementul de pe poziția 3, adică 35. Vedem că este chiar egal cu x, așadar ne oprim și spunem că am găsit elementul.

În loc să facem un maxim de 7 pași (în cel mai rău caz, folosind căutarea secvențială), am făcut doar 3.

Implementarea căutării binare în cod

Cea mai simplă metodă de a implementa căutarea binară este să ne folosim de doi indici suplimentari, st și dr, care să ne spună în ce interval ne aflăm într-un anumit moment. La început, st = 1 și dr = n, însă modificăm aceste valori pe parcurs cu cât tăiem din valori.

Calcularea poziției de mijloc este foarte ușoară: tot ce trebuie să facem este să calculăm media aritmetică a celor două poziții: mij = (st + dr) / 2.

Căutarea binară în C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim valorile în ordinea: lungimea șirului, șirul și valoarea căutată
    int a[100], n, x;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> x;

    int st = 1, dr = n;
    int gasit = -1; //Poziția pe care se află x, respectiv -1 dacă nu se găsește
    while(st <= dr) { //Cât timp avem un interval valid
        int mij = (st + dr) / 2;
        if(a[mij] == x) {
            gasit = mij;
            break;
        } else if(a[mij] < x) {
            st = mij + 1;
        } else {
            dr = mij - 1;
        }
    }

    if(gasit == -1) {
        cout << "Nu am gasit valoarea " << x << " in sir!";
    } else {
        cout << "Valoarea " << x << " se gaseste in sir pe pozitia " << gasit << "!";
    }
    return 0;
}

În această lecție puteți urmări o rezolvare recursivă, pentru clasa a X-a.

Problemă rezolvată

Căutare binară a mai multor valori

Dându-se un șir a cu n numere naturale, ordonate crescător, să se verifice dacă alte m valori se găsesc sau nu în șir. Încarcă soluția ta aici.

Exemplu: Pentru n = 6, șirul a = (2, 4, 7, 8, 8, 9), și cele m = 5 valori: 1, 2, 8, 10, 9, se afișează 0 1 1 0 1.

Rezolvare: Pentru fiecare dintre cele m numere, căutăm binar și afișăm 0 sau 1, în funcție de verdict.

#include <iostream>

using namespace std;

int n, a[100001], m, x;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for(int i = 1; i <= m; i++) {
        cin >> x;
        int gasit = 0, st = 1, dr = n;
        while(st <= dr) {
            int mij = (st + dr) / 2;
            if(a[mij] == x) {
                gasit = 1;
                break;
            } else if(a[mij] < x) {
                st = mij + 1;
            } else {
                dr = mij - 1;
            }
        }
        cout << gasit << " ";
    }
    return 0;
}

Exerciții propuse

Completează următoarele secvențe de cod:

int st = 1, dr = n;
int gasit = -1;
while(!(st ??? dr)) {
    int mij = (st + dr) / 2;

    if(a[mij] == q) gasit = mij;
    else if(a[mij] < q) st = mij + 1;
    else dr = mij - 1;
}

int st = 1, dr = n;
int gasit = -1;
while(st <= dr) {
    int mij = (st + dr) / 2;

    if(a[mij] == x) gasit = mij;
    else if(a[mij] ??? x) st = mij + 1;
    else dr = mij - 1;
}

Probleme propuse

Căutare binară pentru olimpiadă

Atenție la indici

Dacă valorile pentru st și dr sunt valori mari și există riscul de a ieși din tipul de date int atunci când calculăm valoarea de mijloc (întrucât facem suma valorilor st și dr), o alternativă este: mij = st + (dr - st) / 2.

Tip de problemă comună

Pentru olimpiade și concursuri, un tip de problemă care apare des cere găsirea unei valori minime/maxime pentru care o anumită proprietate este respectată: de pildă, problema Buldo de la OJI 2020, clasa a IX-a.

Aici, putem să luăm ca arie de valori pentru H ce trebuie calculat toate numerele de la 1 până la 1.000.000.000. Cum după o anumită valoare proprietatea nu se mai respectă, putem să căutăm binar cea mai mare valoare H pentru care proprietatea este respectată.

Pe aceeași idee există multe alte probleme date la concursuri și olimpiade (chiar și naționale).

Funcții din STL

Există câteva funcții care implementează deja algoritmul de căutare binară. Acestea se găsesc în biblioteca <algorithm> și pot returna următoarele:

#include <algorithm>
...
binary_search(a + 1, a + n + 1, x); //true, dacă x se găsește în a, respectiv false în caz contrar
lower_bound(a + 1, a + n + 1, x); //Pointer către cea mai din stânga poziție din a, egală cu x
upper_bound(a + 1, a + n + 1, x); //Pointer către cea mai din dreapta poziție din a, egală cu x

Bibliografie sau alte resurse

• Căutare binară (Wikipedia)
• Complexitatea unui algoritm
• Algoritm de Căutare Binară (PbInfo)
• Căutarea binară în C++ – Află secretele căutării binare! (InfoGenius)