Algoritmi → Binarna pretraga → Binarna pretraga po rešenju

Binarna pretraga po rešenju

Ideja: monotona provera

Pretpostavimo da imamo funkciju moze(x) koja odgovara sa da/ne i ima osobinu monotonosti: ako je odgovor „da“ za neko x, onda je „da“ i za svako veće x. Tada vrednosti izgledaju ovako:

x:        1   2   3   4   5   6   7   8
moze(x):  ne  ne  ne  ne  da  da  da  da
                          ^ tražimo prvo "da"

Granicu između „ne“ i „da“ nalazimo binarnom pretragom, uz samo log₂(opseg) poziva funkcije moze.

// najmanje x iz [lo, hi] za koje je moze(x) tačno (pretpostavka: moze(hi) je tačno)
long long lo = 1, hi = 1000000000, odgovor = hi;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (moze(mid)) {
        odgovor = mid;      // mid je dobar; probaj manje
        hi = mid - 1;
    } else {
        lo = mid + 1;       // mid nije dobar; treba veće
    }
}

Primer 1: mašine

Zadatak. Fabrika ima n mašina; mašini i treba t[i] sekundi za jedan proizvod, a sve rade istovremeno. Za koje najmanje vreme mogu da naprave ukupno P proizvoda? (n ≤ 2·10⁵, t[i], P ≤ 10⁹)

Provera: za dato vreme T mašina i napravi T / t[i] proizvoda. Ako je zbir bar P, vreme T je dovoljno. Što je više vremena, proizvoda je više – provera je monotona. Gornja granica: najbrža mašina sama napravi P proizvoda za min(t) · P sekundi.

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

int n;
long long P;
vector<long long> t;

bool moze(long long T) {               // da li za T sekundi nastaje bar P proizvoda?
    long long ukupno = 0;
    for (int i = 0; i < n; i++) {
        ukupno += T / t[i];
        if (ukupno >= P) return true;  // prekid i da zbir ne bi prekoračio long long
    }
    return false;
}

int main() {
    cin >> n >> P;
    t.resize(n);
    for (auto &x : t) cin >> x;

    long long lo = 1, hi = *min_element(t.begin(), t.end()) * P, odgovor = hi;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (moze(mid)) { odgovor = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    cout << odgovor << endl;
    return 0;
}

Za prvi primer: za T = 8 mašine naprave 2 + 4 + 1 = 7 proizvoda, a za T = 7 samo 2 + 3 + 1 = 6. Složenost: O(n · log(min(t)·P)) ≈ 60 · n operacija.

Primer 2: testera (najveće dobro x)

Zadatak. Data su stabla visina h[i]. Testera se podesi na visinu H i odseče sve iznad nje: od stabla visine h > H dobija se h − H metara drveta. Koja je najveća visina H uz koju se dobije bar M metara?

Ovde je provera monotona u drugom smeru: što je testera niže, drveta je više. Zato tražimo poslednje „da“: kada je mid dobar, pamtimo ga i idemo desno.

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

int main() {
    int n;
    long long M;
    cin >> n >> M;
    vector<long long> h(n);
    for (auto &x : h) cin >> x;

    long long lo = 0, hi = *max_element(h.begin(), h.end()), odgovor = 0;
    while (lo <= hi) {
        long long H = lo + (hi - lo) / 2;
        long long drvo = 0;
        for (long long x : h)
            if (x > H) drvo += x - H;
        if (drvo >= M) { odgovor = H; lo = H + 1; }   // dovoljno: probaj višu testeru
        else hi = H - 1;                               // premalo: spusti testeru
    }
    cout << odgovor << endl;
    return 0;
}

Binarna pretraga nad realnim brojevima

Kada je odgovor realan broj, umesto lo <= hi ponavljamo korak fiksan broj puta (na primer 100). Svaki korak prepolovi interval, pa posle 100 koraka greška je zanemarljiva. Primer: kvadratni koren broja bez funkcije sqrt.

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

int main() {
    double x;
    cin >> x;                          // x >= 1
    double lo = 0, hi = x;             // koren je u [0, x]
    for (int k = 0; k < 100; k++) {
        double mid = (lo + hi) / 2;
        if (mid * mid >= x) hi = mid;  // mid je dovoljno velik
        else lo = mid;
    }
    cout << fixed << setprecision(6) << hi << endl;
    return 0;
}

Binarnu pretragu nad realnim granicama koristi i zadatak Kružne zone.

Kako prepoznati zadatak?

• Traži se najmanja ili najveća vrednost nečega (vreme, dužina, visina, kapacitet).
• Za zadatu vrednost lako je proveriti da li je „dovoljna“ – obično jednim prolazom kroz niz, često pohlepno.
• Ako je vrednost dovoljna, i svaka veća (ili svaka manja) je dovoljna.

Česte formulacije: „minimizovati maksimum“ (podela niza na k delova sa najmanjim najvećim zbirom) i „maksimizovati minimum“ (rasporediti krave/rutere da najmanje rastojanje bude najveće).

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