Binary & Ternary Search
В тази секция ще разгледаме един от най-фундаменталните и изучавани алгоритми: двоично търсене. Ще видим и какво представлява неговата малка модификация "троично търсене", която ни позволява да намерим максимума на функция, която първо нараства, след което достига търсения максимум, и после намалява (или обратно - да намерим минимума на функция, която първо намалява, стига до него, и после нараства). Макар и относително прости, те са едни от най-често грешените алгоритми, тъй като при невнимание често може да се стигне до off-by-one грешка. Когато се ползват за нецели числа пък трябва да се подходи по малко по-различен начин за да се избегне възникване на проблем в следствие на точността на числата с плаваща запетая.Тъй като двоичното и троичното търсене сами по себе си са относително прости, най-често в състезателни задачи те биват комбинирани с някакъв друг алгоритъм. В следствие на това можете да ги срещнете както в много прости, така и в много сложни задачи - сложността ще се определя именно от този "допълнителен" алгоритъм, който трябва да се приложи.
Темата, която ще ви е безкрайно полезна тук е Двоично търсене, но преди нея можете да погледнете и Разделяй и Владей.
В тази секция задачите ще комбинират двоично търсене с някои от алгоритмите, които вече разгледахме - например итерация, алчен алгоритъм, графов алгоритъм, или проста структура данни. В секциите по-нататък ще видим задачи, в които двоичното търсене е комбинирано с по-сложни алгоритми (като например сложни структури данни, потоци, 2-SAT, хеширане, и други).
Fukushima
8
|
22
Shoe Shopping
37
|
17
Graze
18
|
25
Riddles
26
|
35
SilverGold
10
|
45
Exam
50
|
12
Article
9
|
6
Sysadmin
92
|
32
Load
52
|
42
Increase
35
|
14
Motherboard
14
|
17
ThreeRivers
15
|
52
Socks
35
|
31
Price Change
9
|
14
Deposits
7
|
44
Vitosha
3
|
23