Binarna pretraga

Sećate li se one igre gde vi kažete neki broj, a vaš drug/drugarica kaže da li je broj koji su on/ona zamislili veća ili manja od tog broja, pa naravno da ne. Ali to je u suštini kako binarna pretraga radi. Ona se može koristiti recimo za nalaženje nekog broja u sortiranom nizu mnogo brže ,u složenosti O(log(n) ), nego samo prolaženjem kroz niz. Recimo da se traži neki broj x u nizu A koji je sortiran:

int l,r,m;
bool nadjen(false);
l=0;
r=n-1;
int x;
cin>>x;
while((r>l)&&(!nadjen))
{
m=(l+r)/2;
if(x>a[m])l=m+1;
else if(x<a[m])r=m;
else nadjen=true;
}
if(x==a[n-1])nadjen=true;
if(nadjen)cout<<x<<" postoji\n";
else cout<<x<<" nije nadjen\n";

Uzimamo neki niz recimo 1 10 5 9 16 3 20 17, a tražimo broj 16. Prvo se sortira, i dobije se niz:

0	1	2	3	4	5	6	7
1	3	5	9	10	16	17	20

Na početku leva i desna granica su l=0 i r=7. Uzimamo srednji indeks m=3. Pošto je 16>9 sada je l=4. Novi srednji indeks je m=5. 16==16 i u tom slučaju dešava se da je nadjen=true, i uslov !nadjen postaje false, odnosno petlja se prekida.

Kada bi smo tražili broj 14. Kažemo da je l=0 i r=7. U prvom koraku m=3, 14>9 oa je l=4. U sledećem koraku m=5, a 14<16 sledi r=5. Sada je m=4, a pošto je 14>10 sledi l=5, nailazimo na trenutak kada je l==r, tada se petlja prekida i ispisu je se "nije nadjen".

Evo jednog primera za vežbu: Napišite program za uneta dva niza (A i Q) ispisuje za svaki član iz niza Q, da li postoji taj broj u nizu A, koristeći binarnu pretragu.