3.6 Binarna pretraga

Binarno pretraživanje ili binarna pretraga je algoritam pretrage uređene (sortirane) serije elemenata. Najčešće se (ali ne uvek) proverava da li niz sadrži datu vrednosti). Nakon poređenja tražene vrednosti sa središnjim elementom niza, zahvaljujući sortiranosti niza, može se izvršiti odbacivanje (tj. odsecanje) jedne polovine niza i pretraga se nastavlja u drugoj polovini. Ovo polovljenje dužine niza u svakom koraku dovodi do veoma efikasnog postupka (pokazaćemo da je broj koraka \(O(\log{n})\), gde je \(n\) broj elemenata serije).

U osnovnoj varijanti, binarna pretraga služi da se proveri da li sortirani niz elemenata sadrži neku datu vrednost. Pored ovoga, binarna pretraga se može upotrebiti da se pronađe prvi element u sortiranom nizu koji je (bilo strogo, bilo nestrogo) veći ili manji od date vrednosti. U svom najopštijem obliku binarna pretraga se koristi da se u nizu pronađe tzv. prelomna tačka: ako se zna da su elementi uređeni tako da prvo idu oni koji ne zadovoljavaju neko svojstvo \(P\), a zatim oni koji zadovoljavaju svojstvo \(P\), moguće je efikasno pronaći prvi element koji to svojstvo zadovoljava ili poslednji element koji ne zadovoljava to svojstvo.

Standardna biblioteka jezika C++ nudi nekoliko funkcija koje sprovode algoritam binarne pretrage.

• Funkcija binary_search proverava da li dati segment elemenata (zadat pomoću dva iteratora) sortiranog niza (tj. vektora)¹ sadrži zadatu vrednost (funkcija vraća true ako i samo ako se tražena vrednost nalazi unutar zadatog segmenta). Provera da li se data vrednost x nalazi unutar sortiranog niza (ili vektora) a može se izvršiti pomoću binary_search(begin(a), end(a), x).
• Ako je potrebno u sortiranom nizu (tj. vektoru) pronaći sve elemente jednake datom elementu, možemo koristiti funkciju equal_range (sa istim parametrima kao binary_search). Ona vraća par iteratora koji ograničavaju segment elemenata jednakih datom (prvi iterator ukazuje na prvi element jednak traženoj vrednosti, a drugi na poziciju neposredno iza poslednjeg elementa jednakog traženoj vrednosti).
• Funkcija lower_bound vraća prvi od ta dva iteratora (tj. prvi element sortiranog niza (tj. vektora) tj. nekog njegovog segmenta koji je veći ili jednak od tražene vrednosti).
• Funkcija upper_bound vraća drugi od njih (tj. prvi element sortiranog niza (tj. vektora) tj. nekog njegovog segmenta koji je strogo veći od tražene vrednosti).

Ako se ne zada drugačije, ove funkcije podrazumevaju se da je niz sortiran u odnosu na podrazumevani poredak elemenata (neopadajući numerički ako su brojevi u pitanju, tj. neopadajući abecedni leksikografski ako su niske u pitanju). Poredak se može zadati ili promeniti na sličan način kao kod funkcija za sortiranje.

I ručna implementacija algoritma binarne pretrage je prilično jednostavna, a potrebno ju je koristiti kada se pretražuje serija brojeva koji nisu smešteni u nizu (na primer, kada se binarnom pretragom traži optimalna vrednost neke funkcije, o čemu će biti reči u poglavljima 3.6.3 i 3.6.4) ili kada je potrebno algoritam prilagoditi nekom problemu. Stoga ćemo u nastavku prikazati i ručne implementacije ovog algoritma.

3.6.1 Traženje vrednosti u nizu

Opišimo prvo osnovnu varijantu algoritma u kojoj se u sortiranom nizu (tj. vektoru) traži pozicija na kojoj se pojavljuje neka zadata vrednost.

Provera da li neopadajuće sortiran niz sadrži datu vrednost se može lako izvršiti bibliotečkom funkcijom binary_search.

vector<int> a = {1, 8, 13, 15, 15, 23, 38, 38, 38, 42};
int x = 15;
if (binary_search(begin(a), end(a), x))
   cout << "Sadrzi" << endl;
else
   cout << "Ne sadrzi" << endl;

Opišimo sada i kako binarna pretraga može da se implementira. Ako sortirani niz u kojem tražimo zadati element ima konačni broj elemenata, binarno pretraživanje se vrši na sledeći način: pronalazi se središnji element (element na središnjoj poziciji) dela niza koji se pretražuje, proverava se da li je on jednak zadatoj vrednosti i ako jeste – vraća se njegov indeks, a ako nije – pretraživanje se nastavlja nad delom niza levo od središnjeg elementa, u kojem su svi manji elementi (ako je središnji element veći od zadate vrednosti) ili u delu niza desno od središnjeg elementa, u kojem su svi veći elemenati (ako je središnji element manji od zadate vrednosti). Dakle, u svakom koraku, sve dok se ne pronađe tražena vrednost, niz se deli se na dva dela i pretraga se nastavlja samo u jednom njegovom delu — odbacuje se deo koji sigurno ne sadrži traženu vrednost. Binarno pretraživanje je, stoga, primer pristupa podeli i vladaj (engl. divide and conquer), koji će detaljnije biti opisan u poglavlju 5. Pošto se jedna polovina elemenata eliminiše, ponekad se ovaj pristup naziva i smanji i vladaj (engl. decrease and conquer).

Generalno, broj potrebnih pitanja tj. koraka binarne pretrage je reda \(O(\log n)\), gde je \(n\) širina polaznog intervala koji se pretražuje. Naime, posle prvog pitanja širina sa \(n\) opada na \(\frac{n}{2}\), posle sledećeg na \(\frac{n}{4}\) itd. Posle \(k\) pitanja širina intervala opada na \(\frac{n}{2^k}\). Pošto se pretraga vrši sve dok interval ne postane jednočlan ili prazan, važi da je \(\frac{n}{2^k} \leq 1\), tj. da se odgovor dobija kada \(k\) dostigne vrednost približno jednaku \(\log_2 n\).

Binarno pretraživanje je moguće primeniti i kada nije unapred poznata dužina sortiranog niza koji se pretražuje. Tada se u prvoj fazi određuje gornja granica dela niza u kom bi traženi element mogao da se nađe (pronalazi se prva vrednost veća ili jednaka od tražene), da bi se u drugoj fazi primenila klasična binarna pretraga.

Binarno pretraživanje daleko je efikasnije nego linearno, ali zahteva da su podaci koji se pretražuju uređeni. To je i jedan od glavnih razloga da se u rečnicima, enciklopedijama, štamapnim telefonskim imenicima kakvi su se koristili u doba fiksne telefonije i slično odrednice sortiraju. Ovakve knjige obično se pretražuju postupkom koji odgovara varijantama binarne pretrage². Odnos složenosti postaje još očigledniji ukoliko se zamisli koliko bi komplikovano bilo sekvencijalno pretraživanje reči u nesortiranom rečniku.

Binarno pretraživanje može se implementirati iterativno ili rekurzivno.

Naredna implementacija binarnog pretraživanja poziva pomoćnu, rekurzivnu funkciju binarna_pretraga koja rešava nešto opštiji zadatak – vraća indeks elementa niza a između indeksa l i indeksa d (uključujući i njih) koji je jednak zadatoj vrednosti x ako takav postoji, a vraća -1 inače.

int binarna_pretraga(const vector<int>& a, int l, int d, int x)
{
  int s;
  if (l > d)
    return -1;
  s = l + (d - l)/2;
  if (x < a[s])
    return binarna_pretraga(a, l, s-1, x);
  else if (x > a[s])
    return binarna_pretraga(a, s+1, d, x);
  else /* if (x == a[s]) */
    return s;
}

int binarna_pretraga(const vector<int>& a, int x) {
  int n = a.size();
  return binarna_pretraga(a, 0, n-1, x);
}

Primetimo da se, umesto izraza l + (d - l)/2, za određivanje središnjeg indeksa može koristiti i kraći izraz (l + d) / 2. Ipak, upotreba prvog izraza je preporučena kako bi se smanjila mogućnost nastanka prekoračenja. Ovo je jedan od mnogih primera gde izrazi koji su matematički jednaki, imaju različita svojstva u aritmetici fiksne širine.

Složenost navedene funkcije je \(O(\log n)\), a njena korektnost dokazuje se jednostavno (indukcijom), pri čemu se pretpostavlja da je niz a sortiran.

Rekurzivna funkcija se zaustavlja jer vrednost \(d-l\) opada u svakom rekurzivnom pozivu, a važi \(d - l \geq -1\), pa se to opadanje mora u nekom trenutku završiti.

U glavnom pozivu funkcije su ispunjeni uslovi prethodnog tvrđenja (indeksi \(0\) i \(n-1\) su u zahtevanim granicama), pa je i glavna funkcija korektna.

Umesto rekurzivne, implementacija može biti i iterativna.³

int binarna_pretraga(const vector<int>& a, int x) {
  int l, d, s;
  l = 0; d = a.size() - 1;
  while (l <= d) {
    s = l + (d - l)/2;
    if (x < a[s])
      d = s - 1;
    else if (x > a[s])
      l = s + 1;
    else if (x == a[s])
      return s;
  }
  return -1;
}

Njen dokaz korektnosti (ostavljen čitaocu za vežbu) se zasniva na invarijanti da su elementi levo od pozicije \(l\) strogo manji od \(x\), a desno od pozicije \(d\) strogo veći od \(x\).

3.6.2 Traženje prelomne tačke

Osnovna varijanta binarne pretrage, čija je implementacija prikazana, pronalazi datu vrednost u sortiranom nizu. Kao što je već nagovešteno, binarna pretraga može se upotrebiti i za rešavanje nešto opštijih problema. Pretpostavimo da je niz uređen tako da svi njegovi početni elementi zadovoljavaju neki uslov \(P\), a da posle njih idu elementi koji ne zadovoljavaju taj uslov. Takav niz možemo neformalno predstaviti nizom pluseva (koji označavaju elemente koji zadovoljavaju svojstvo \(P\)), a zatim minusa (koji označavaju elemente koji ne zadovoljavaju svojstvo \(P\)). Na primer, +++++----. Potrebno pronaći mesto u nizu gde se ta promena dešava (tj. potrebno je pronaći poslednji element koji zadovoljava uslov \(P\) tj. poslednji + ili prvi element koji ga ne zadovoljava tj. prvi -). Na primer, može biti poznato da se u nizu nalaze prvo parni, a zatim neparni elementi i potrebno je pronaći koliko postoji svakih. Slično, može se razmatrati sortiran niz i za uslov \(P\) uzeti uslov da je element niza strogo manji od neke date vrednosti \(x\) (u sortiranom nizu, prvo su svi elementi koji su strogo manji od \(x\), a iza njih su elementi koji su veći od ili jednaki \(x\)).

Problem traženja prelomne tačke opštiji je od problema traženja zadate vrednosti u sortiranom nizu, jer se u ovom drugom problemu podrazumeva postojanje relacije poretka na osnovu koje su vrednosti u nizu sortirane, dok se u prvom problemu podrazumevamo samo tzv. svojstvo monotonosti, koje podrazumeva da se u nizu prvo javljaju elementi koji zadovoljavaju neko svojstvo \(P\), pa onda oni koji ga ne zadovoljavaju. Da bi se dokazalo da niz zadovoljava svojstvo monotonosti, dovoljno je dokazati bilo koji od sledeća dva (ekvivalentna) uslova:

• Za svake dve pozicije \(0 \leq i < j < 0\), ako element na poziciji \(j\) ima svojstvo \(P\), onda i element na poziciji \(i\) ima svojstvo \(P\).
• Za svake dve pozicije \(0 \leq i < j < 0\), ako element na poziciji \(i\) nema svojstvo \(P\), onda i element na poziciji \(j\) nema svojstvo \(P\).

Kao ilustraciju varijante binarne pretrage u kojoj se pronalazi takva prelomna tačka, u nastavku je prikazana funkcija koja pronalazi poziciju prvog elementa u sortiranom nizu koji je veći od ili jednak datoj vrednosti \(x\) (ili vraća dužinu niza ako takav element ne postoji). Ovo je tačno ono što radi bibliotečke funkcija lower_bound. Na sličan način može se odrediti i pozicija prvog elementa koji je strogo veći od zadatog broja, poslednjeg elementa koji je manji od ili jednak datom broju ili poslednjeg elementa koji strogo manji od datog broja.

vector<int> a = {1, 8, 13, 15, 15, 23, 38, 38, 38, 42};
int x = 16;
// prvi element veci ili jednak od 16 je 23 (na poziciji 6)
auto it = lower_bound(begin(a), end(a), x);
cout << distance(begin(a), it) << endl;

Binarna pretraga prelomne tačke može se jednostavno iskoristi i za proveru da li niz sadrži dati broj. Kada se nađe pozicija prvog elementa koji je veći od ili jednak od traženog, jednostavno se može proveriti da li se na toj poziciji nalazi upravo taj element (ako postoji u nizu, on mora biti na toj poziciji). Ako vrednost postoji u nizu, to će biti tražena pozicija, a ako ne postoji, onda će iterator koji funkcija lower_bound vraća biti ili van granica niza (ako su svi elementi niza manji od tražene vrednosti) ili će ukazivati na element koji je strogo veći od tražene vrednosti.

vector<int> a = {1, 8, 13, 15, 15, 23, 38, 38, 38, 42};
int x = 15;
auto it = lower_bound(begin(a), end(a), x);
if (it < end(a) && *it == x)
   cout << "Na poziciji: " << distance(begin(a), it) << endl;
else
   cout << "Ne sadrzi" << endl;

Korišćenjem funkcije lower_bound može se, na primer, odrediti i broj elemenata koji su veći od ili jednaki datom elementu u nekom sortiranom nizu (u opštem slučaju može se pronaći broj elemenata koji zadovoljavaju i broj elemenata koji ne zadovoljavaju uslov \(P\)).

int broj_vecih_ili_jednakih(const vector<int>& a, int x)  {
  auto it = lower_bound(begin(a), end(a), x);
  return  distance(it, end(a));
}

Broj jednakih elemenata jednakih datoj vrednosti x se može pronaći funkcijom equal_range ili kombinacijom funkcija lower_bound i upper_bound tako što se nađe pozicija prvog elementa većeg ili jednakog od x i pozicija prvog elementa strogo većeg od x. Razlika te dve pozicije daje traženi broj pojavljivanja vrednosti x.

int broj_pojavljivanja(const vector<int>& a, int x) 
{
   auto lb = lower_bound(begin(a), end(a), x);
   auto ub = upper_bound(begin(a), end(a), x);
   return distance(lb, ub);
}

Pređimo sada na ručnu implementaciju pretrage prelomne tačke. Umesto da prikažemo implementaciju ove funkcije, a zatim da dokažemo njenu korektnost, pokušajmo da funkciju izvedemo iz specifikacije tj. nametnute invarijante. Uvedimo promenljive \(l\) i \(d\) i osigurajmo, kao invarijantu, da sve vreme tokom pretrage važe sledeći uslovi:

• Elementi niza \(a\) na pozicijama iz intervala \([0, l)\) manji od vrednosti \(x\) (zadovoljavaju uslov \(P\)),
• da su elementi na pozicijama iz intervala \((d, n)\) veći od ili jednaki \(x\) (ne zadovoljavaju uslov \(P\)).

Elementima na pozicijama iz intervala \([l, d]\) status još nije poznat (ovo formalno nije deo invarijante, mada važi tokom pretrage).

Raspored je, dakle, sledeći:

• Ovi uslovi će biti na početku ispunjeni, ako se promenljiva \(l\) inicijalizuje na nulu (tada je interval \([0, l) = [0, 0)\) prazan), a promenljiva \(d\) na vrednost \(n-1\) (tada je i interval \((d, n) = (n-1, n)\) prazan).

• Neka \(s\) predstavlja sredinu intervala \([l, d]\).

  • Ako je element niza \(a\) na poziciji \(s\) manji od vrednosti \(x\) (zadovoljava uslov \(P\)) takvi su i svi elementi iz intervala \([l, s]\). Zato se vrednost \(l\) može postaviti na \(s+1\) i invarijanta će ostati da važi (zaista, ako je \(l' = s+1\), svi elementi sa pozicija iz intervala \([0, l')\) će biti ili sa pozicija iz intervala \([0, l)\) za koje se zna da su manji od \(x\) (zadovoljavaju uslov \(P\)) ili su iz sa pozicija iz intervala \([l, s]\), za koje je upravo utvrđeno da su manji od \(x\) tj. da zadovoljavaju uslov \(P\)).

  • Ako je element niza na poziciji \(s\) veći od ili jednak \(x\) (ne zadovoljava uslov \(P\)), tada su i svi elementi na pozicijama iz intervala \([s, d]\) veći od ili jednaki \(x\) (i ne zadovoljavaju uslov \(P\)). Zato se vrednost \(d\) može postaviti na \(s-1\) i invarijanta će ostati da važi (zaista, ako je \(d' = s-1\), tada su svi elementi iz intervala pozicija \((d', n)\) ili iz intervala \([s, d]\) za koje je upravo utvrđeno da će biti veći od ili jednaki \(x\) ili iz intervala \((d, n)\) za koje se od ranije zna da su veći od ili jednaki \(x\)).

Pretraga se vrši sve dok postoje elementi nepoznatog statusa, tj. sve dok je interval \([l, d]\) neprazan, odnosno dok je \(l \leq d\). U trenutku kada važi \(l > d\), na osnovu invarijante sledi:

• Svi elementi levo od \(l\) zadovoljavaju uslov \(P\), pa se poslednji takav element mora nalaziti na poziciji \(l-1=d\).

• Svi elementi desno od \(d\) ne zadovoljavaju uslov \(P\), pa se prvi takav element nalazi na poziciji \(d+1 = l\). Dakle, prvi element veći ili jednak od datog broja \(x\) se nalazi na poziciji \(l\).

int prvi_veci_ili_jednak(const vector<int>& a, int n, int x)  {
  int l = 0, d = n-1;
  while (l <= d) {
    int s = l + (d - l) / 2;
    if (a[s] < x) {
      l = s + 1;
    } else
      d = s - 1;
  }
  return l;
}

Zadatak: Broj studenata iznad praga

Komisija za upis na fakultet treba da odredi prag za upis kandidata. Komisiju stalno pitaju koji bi broj studenata bio upisan kada bi prag prolaznosti bio zadati broj poena (upisuju se svi kandidati čiji je broj poena veći ili jednak pragu). Potrebno je napisati program koji daje odgovore na ta pitanja.

Opis ulaza

Sa standardnog ulaza učitava se broj kandidata \(n\) (\(0 \leq n \leq 10^5\)), a zatim i njihovi takmičara (celi brojevi), zadati u sortiranom redosledu od najvećeg do najmanjeg. Nakon toga se učitava broj \(m\) (\(1 \leq m \leq 50000\)) koji predstavlja broj pitanja na koja treba da se odgovori, a zatim i \(m\) brojeva za koje je potrebno dati odgovor koliko bi se studenata upisalo kada bi se taj broj poena uzeo za prag.

Opis izlaza

Na standardni izlaz ispisati tražene brojeve upisanih studenata, svaki u posebnom redu.

Primer

Ulaz

5
89 73 73 56 23
4
95 50 70 0

Izlaz

0
4
3
5

Rešenje

U zadatku je potrebno efikasno odrediti broj elemenata sortiranog niza koji su veći ili jednaki od datog broja. Ako nađemo poziciju prvog elementa koji je veći ili jednak od datog broja, tada broj takvih elemenata možemo odrediti tako što izračunamo razliku između ukupnog broja članova niza i te pozicije.

Linearna pretraga

Najjednostavniji način da nađemo poziciju prvog elementa koji je veći ili jednak od datog broja je da primenimo linearnu pretragu i da redom proveravamo jedan po jedan element sve dok ne dođemo ili do kraja niza ili do tražene pozicije.

Složenost ovakve pretrage je \(O(n)\), pa je ukupna složenost rešenja \(O(m\cdot n)\), što je previše imajući u vidu ograničenja data u zadatku.

Binarna pretraga

Pozicija se efikasno može pronaći primenom algoritma binarne pretrage. Najjednostavnije je upotrebiti bibliotečku implementaciju. U jeziku C++ možemo upotrebiti funkciju lower_bound.

Složenost jedne binarne pretrage je \(O(\log{n})\), pa je ukupna složenost algoritma \(O(m \log{n})\).

int m;
cin >> m;
for (int i = 0; i < m; i++) {
 int prag;
 cin >> prag;
 auto it = lower_bound(begin(poeni), end(poeni), prag);
 int broj = distance(it, end(poeni));
 cout << broj << endl;
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;


int main() {
  int n;
  cin >> n;
  vector<int> poeni(n);
  for (int i = n-1; i >= 0; i--)
    cin >> poeni[i];

  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
   int prag;
   cin >> prag;
   auto it = lower_bound(begin(poeni), end(poeni), prag);
   int broj = distance(it, end(poeni));
   cout << broj << endl;
  }
  
  return 0;
}

Zadatak: Minimum rotiranog sortiranog niza

Sortirani niz celih brojeva u kome su svi elementi različiti je rotiran za \(k\) mesta ulevo i time je dobijen ciklični niz koji zadovoljava uslov da je \(x_k < x_{k+1} < \ldots < x_{n-1} < x_0 < \ldots < x_{k-1}\). Jedan takav niz je, na primer, 11 13 15 19 24 1 3 8 9. Napisati program koji pronalazi najmanji element takvog niza. Potrudi se da se nakon učitavanja elemenata minimum pronađe u vremenskoj složenosti \(O(\log{n})\).

Opis ulaza

Sa standardnog ulaza se učitava broj \(n\) (\(1 \leq n \leq 50000\)), a zatim \(n\) elemenata niza (\(n\) celih brojeva razvojenih sa po jednim razmakom).

Opis izlaza

Na standardni izlaz ispisati najmanji element niza.

Primer

Ulaz

9
11 13 15 19 24 1 3 8 9

Izlaz

1

Rešenje

Linearna pretraga

Zadatak možemo rešiti uobičajenim algoritmom ili bibliotečkom funkcijom za pronalaženja minimuma. U jeziku C++ možemo upotrebiti funkciju min_element.

Ovaj algoritam zahteva prolazak kroz sve elemente niza, pa je složenosti \(O(n)\).

Binarna pretraga

Poređenje se poslednjim elementom niza

Bolje rešenje se može dobiti binarnom pretragom. Nakon rotacije svi elementi u početnom delu niza su strogo veći od početnog, a onda u završnom delu niza idu svi elementi koji su strogo manji od poslednjeg. Najmanji element koji tražimo je prvi element u nizu koji je strogo manji od poslednjeg i njega možemo naći binarnom pretragom.

Invarijanta ovog algoritma je da su:

• svi elementi ispred pozicije \(l\) (elementi na pozicijama iz intervala \([0, l)\)) strogo veći od poslednjeg elementa niza i sortirani su,
• svi elemeni iza pozicije \(d\) (elementi na pozicijama iz intervala \((d, n)\)) manji ili jednaki od poslednjeg elementa niza i sortirani su.

Kada se petlja završi važi da je \(l = d+1\). Zato su svi elementi iza pozicije \(l\) strogo veći od elemenata na poziciji \(l\). Pošto je deo od pozicije \(l\) do kraja sortiran, minimum se nalazi na poziciji \(l\), jer je taj deo uvek neprazan. Zaista, mora da važi da je \(l < n\), jer bi u suprotnom poslednji element bio levo od pozicije \(l\), što je nemoguće, jer se levo od pozicije \(l\) nalaze elementi koji su strogo veći od poslednjeg.

int minRotiranogSortiranog(const vector<int>& a) {
  int n = a.size();
  int l = 0, d = n-1;
  while (l <= d) {
    int s = l + (d-l)/2;
    if (a[s] < a[n-1])
      d = s-1;
    else
      l = s+1;
  }
  return a[l];
}

#include <iostream>
#include <vector>

using namespace std;

int minRotiranogSortiranog(const vector<int>& a) {
  int n = a.size();
  int l = 0, d = n-1;
  while (l <= d) {
    int s = l + (d-l)/2;
    if (a[s] < a[n-1])
      d = s-1;
    else
      l = s+1;
  }
  return a[l];
}

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

  cout << minRotiranogSortiranog(a) << endl;

  return 0;
}

3.6.3 Optimizacija binarnom pretragom (pretraga po rešenju)

Binarna pretraga se može upotrebiti i u procesu optimizacije, ako se problem može formulisati kao problem pronalaženja prelomne tačke. Ovaj oblik pretrage se ponekad naziva binarna pretraga po rešenju, jer se prostor kome može pripadati vrednost rešenja problema binarno pretražuje. Ideja je da se problem optimizacije “naći najmanju vrednost koja zadovoljava određeni uslov”, svede na problem odlučivanja “da li data vrednost zadovoljava određeni uslov”. Binarnu pretragu je moguće primeniti ako problem zadovoljava svojstvo monotonosti, koje zahteva da ako neka vrednost zadovoljava uslov, onda uslov zadovoljavaju i sve vrednosti veće od nje, a ako ne zadovoljava, onda uslov ne zadovoljavaju ni vrednosti manje od nje. Naravno, sasvim sličan je zadatak pronalaženja najveće vrednosti koja ne zadovoljava uslov. Karakteristično za ovu upotrebu binarne pretrage je to što vrednosti o kojima je reč obično nisu indeksi elemenata niza, a često se vrši optimizacija i nad neprekidnim skupom vrednosti (do na određenu tačnost). Takođe, provera ispunjenja uslova za svaku konkretnu vrednost je obično spora i želimo da smanjimo broj provera ispunjenja uslova koliko je moguće. Stoga se u ovakvim situacijama umesto korišćenja bibliotečkih funkcija, binarna pretraga implementira ručno.

Ilustrujmo ovu tehniku kroz sledeći problem.

Zadatak: Drva

Drvoseča treba da naseče određenu količinu drveta i ima testeru koju može da podešava da seče na bilo kojoj celobrojnoj visini (u metrima). Pošto testera seče samo drvo iznad visine na koju je postavljena, što je testera više, naseći će se manje drveta. Pošto drvoseča brine o okolini, on ne želi da naseče više drveta nego što mu je potrebno. Napiši program koji određuje najvišu moguću celobrojnu visinu testere, tako da drvoseča dobije dovoljno drveta (pretpostavi da uvek postoji dovoljno drveta).

Opis ulaza

Sa standardnog ulaza se učitava broj drveća u šumi \(n\) (\(1 \leq n \leq 10^5\)), a zatim niz visina svakog drveta (niz prirodnih brojeva između 1 i \(10000\), razdvojenih sa po jednim razmakom). Nakon toga učitava se i količina nasečenog drveta (pošto su sva debla iste debljine, količina se meri u metrima visine isečenih stabala).

Opis izlaza

Na standardni izlaz ispisati traženu maksimalnu celobrojnu visinu testere.

Primer

Ulaz

5
24 21 19 14 22
14

Izlaz

18

Objašnjenje

Postavljanjem testere na 18 metara, od prvog drveta ćemo odseći 6 metara, od drugog 3, od trećeg 1, od četvrtog ništa, a od petog 4 metra. To je ukupno 14 metara, što je tačno onoliko koliko mu je potrebno.

Rešenje

Optimizacija binarnom pretragom

Zadatak se može rešiti korišćenjem binarne pretrage po rešenju tj. po traženju optimalne vrednosti korišćenjem binarne pretrage (nad segmentom od najmanje do najveće visine testere). Primetimo da u ovom slučaju nemamo vrednosti unapred zadate u nizu, štaviše niz neće ni biti potreban. Takođe, neće biti ni izračunate vrednosti za sve moguće visine, već samo za neke, po potrebi.

Postavljanjem testere na visinu \(h\), kod svih drva koja su viša od \(h\) biće odsečeno \(h_i - h\) metara, dok od ostalih drva neće biti isečeno ništa. Na osnovu toga, za fiksiranu visinu testere grubom silom (ispitivanjem svakog drveta zasebno) u vremenu \(O(n)\) možemo izračunati ukupnu količinu nasečenog drveta. Binarna pretraga je primenljiva jer znamo da je do određenih visina testere drveta dovoljno, a da je od određene visine testere drveta premalo, tako da zapravo tražimo prelomnu tačku, tj. najveću visinu testere za koju je drveta dovoljno tj.  poslednji element niza koji zadovoljava uslov.

Ako je maksimalna visina drveta \(M\), tada je složenost ovog pristupa \(O(n \log{M})\). Naime, binarnom pretragom se pretražuje interval \([0, M]\), pa se provera da li je nasečeno dovoljno drveta poziva \(\log{M}\) puta. Izračunavanje količine nasečenog drveta i provera da li je ona dovoljna vrši se jednim prolazak kroz niz drveta i složenosti je \(O(n)\).

int testera(const vector<int>& visine, int potrebno) {
  int od_visina = 0;
  int do_visina = *max_element(begin(visine), end(visine));
  while (od_visina <= do_visina) {
    int visina = od_visina + (do_visina - od_visina) / 2;
    long long naseceno = 0;
    for (int v : visine)
      if (v >= visina)
        naseceno += v - visina;

    if (naseceno >= potrebno)
      od_visina = visina + 1;
    else
      do_visina = visina - 1;
  }
  return do_visina;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int testera(const vector<int>& visine, int potrebno) {
  int od_visina = 0;
  int do_visina = *max_element(begin(visine), end(visine));
  while (od_visina <= do_visina) {
    int visina = od_visina + (do_visina - od_visina) / 2;
    long long naseceno = 0;
    for (int v : visine)
      if (v >= visina)
        naseceno += v - visina;

    if (naseceno >= potrebno)
      od_visina = visina + 1;
    else
      do_visina = visina - 1;
  }
  return do_visina;
}

int main() {
  int n;
  cin >> n;
  vector<int> visina(n);
  for (int i = 0; i < n; i++)
    cin >> visina[i];
  long long potrebno;
  cin >> potrebno;

  cout << testera(visina, potrebno) << endl;

  return 0;
}

3.6.4 Određivanje nulu, minumum ili maksimum realne funkcije

Binarnom pretragom možemo odrediti neke značajne tačke realne funkcije (nule, minimum, maksimum), do na određenu tačnost. Na primer, jednačinu \(\cos(x) = x\), možemo rešiti sa tačnošću \(10^{-5}\) narednim postupkom.

double l = 0, d = 1;
while (abs(d - l) >= 1e-5) {
  double s = (l + d) / 2;
  if (cos(s) > s)
      l = s;
  else
      d = s;
}
cout << (l + d) / 2 << endl;