Algoritmi → Binarna pretraga → Binarna pretraga

Binarna pretraga

Linearna pretraga

Najjednostavniji način da proverimo da li se broj x nalazi u nizu je da redom pogledamo sve elemente:

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    int a[1000];
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;

    int poz = -1;                    // -1 znači: nije pronađen
    for (int i = 0; i < n; i++) {
        if (a[i] == x) {
            poz = i;
            break;                   // našli smo ga, prekidamo petlju
        }
    }
    cout << poz << endl;
    return 0;
}

Linearna pretraga radi i za nesortiran niz, ali u najgorem slučaju pregleda svih n elemenata – složenost je O(n). Ako u istom nizu tražimo mnogo brojeva (na primer 10⁵ upita u nizu od 10⁵ elemenata), to je 10¹⁰ koraka – predugo.

Ideja binarne pretrage

Kada je niz sortiran, dovoljno je pogledati srednji element a[s]:

• ako je a[s] == x – pronašli smo ga;
• ako je x < a[s] – traženi broj može biti samo levo od sredine, pa desnu polovinu odbacujemo;
• ako je x > a[s] – može biti samo desno, pa odbacujemo levu polovinu.

Isto kao kada tražiš reč u rečniku: otvoriš ga na sredini i odmah znaš da li treba da ideš napred ili nazad.

Program

#include <iostream>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    int a[100000];
    for (int i = 0; i < n; i++) cin >> a[i];   // niz je sortiran rastuće
    cin >> x;

    int l = 0, d = n - 1, poz = -1;   // tražimo u intervalu [l, d]
    while (l <= d) {                  // dok interval nije prazan
        int s = l + (d - l) / 2;      // sredina intervala
        if (a[s] == x) {
            poz = s;                  // pronađen
            break;
        } else if (x < a[s]) {
            d = s - 1;                // nastavljamo u [l, s-1]
        } else {
            l = s + 1;                // nastavljamo u [s+1, d]
        }
    }
    cout << poz << endl;
    return 0;
}

Koliko koraka?

Posle svakog koraka interval se bar prepolovi: n → n/2 → n/4 → … → 1. Broj koraka je oko log₂ n – složenost je O(log n).

Ako niz nije sortiran, prvo ga sortiramo (sort, O(n log n)) – to se isplati kada je upita mnogo.

Varijanta: prvo pojavljivanje

Ako se x javlja više puta, osnovna verzija vraća neku od njegovih pozicija. Često nam treba prva. Tada, kada nađemo x, zapamtimo poziciju i nastavimo da tražimo levo:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, x;
    cin >> n;
    vector<int> a(n);
    for (int &v : a) cin >> v;
    cin >> x;

    int l = 0, d = n - 1, poz = -1;
    while (l <= d) {
        int s = l + (d - l) / 2;
        if (a[s] >= x) {
            if (a[s] == x) poz = s;   // kandidat; možda postoji i raniji
            d = s - 1;                // nastavi levo
        } else {
            l = s + 1;
        }
    }
    cout << poz << endl;
    return 0;
}

Za ovakve zadatke C++ ima gotove funkcije lower_bound i upper_bound – o njima je sledeća lekcija.

Primer: znak u sortiranoj niski

Binarna pretraga radi nad bilo kojim sortiranim nizom, pa i nad niskom čiji su znaci poređani po ASCII kodovima. Program proverava da li sortirana niska (najviše 20 znakova) sadrži znak @:

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;                         // znaci su sortirani po ASCII kodu
    char trazeni = '@';
    int l = 0, d = (int)s.size() - 1, poz = -1;
    while (l <= d) {
        int m = (l + d) / 2;
        if (s[m] == trazeni) { poz = m; break; }
        if (trazeni < s[m]) d = m - 1;
        else l = m + 1;
    }
    if (poz >= 0) cout << "Znak @ je na poziciji " << poz << endl;
    else cout << "Znak nije pronađen" << endl;
    return 0;
}

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje