Vodič · Algoritmi · Binarna pretraga
Binarna pretraga – vodič kroz lekcije
Binarna pretraga je algoritam koji svakim korakom prepolovi prostor pretrage. U nizu od milijardu elemenata nalazi traženi broj u 30 koraka.
Osim traženja u nizu, ista ideja rešava i optimizacione zadatke: „koliko je najmanje vremena potrebno…“, „koja je najveća moguća visina…“ – to je binarna pretraga po rešenju, jedna od najčešćih tehnika na takmičenjima.
- 6–8. razred i srednja škola
- C++
- Priprema za takmičenja
Najvažnije pravilo: binarna pretraga radi samo nad monotonim podacima – sortiranim nizom ili proverom koja se, kada jednom postane tačna, više ne menja.
1 Binarna pretraga u nizu
Algoritam, granice i najčešće greške.
2 Gotove funkcije
Kako se binarna pretraga piše u jednom redu.
3 Binarna pretraga po rešenju
Kada je lakše proveriti odgovor nego ga izračunati.
4 Šta dalje
Tehnike koje se često kombinuju sa binarnom pretragom.
Predloženi redosled
Korisni spoljni resursi
- CSES Problem Set – odeljak „Sorting and Searching“, zadaci sa automatskom proverom
- USACO Guide – Binary Search – objašnjenja i zadaci po težini (engleski)
- Petlja – zbirke zadataka na srpskom sa automatskom proverom