Binary & Ternary Search

В тази секция ще разгледаме един от най-фундаменталните и изучавани алгоритми: двоично търсене. Ще видим и какво представлява неговата малка модификация "троично търсене", която ни позволява да намерим максимума на функция, която първо нараства, след което достига търсения максимум, и после намалява (или обратно - да намерим минимума на функция, която първо намалява, стига до него, и после нараства). Макар и относително прости, те са едни от най-често грешените алгоритми, тъй като при невнимание често може да се стигне до off-by-one грешка. Когато се ползват за нецели числа пък трябва да се подходи по малко по-различен начин за да се избегне възникване на проблем в следствие на точността на числата с плаваща запетая.

Тъй като двоичното и троичното търсене сами по себе си са относително прости, най-често в състезателни задачи те биват комбинирани с някакъв друг алгоритъм. В следствие на това можете да ги срещнете както в много прости, така и в много сложни задачи - сложността ще се определя именно от този "допълнителен" алгоритъм, който трябва да се приложи.

Темата, която ще ви е безкрайно полезна тук е Двоично търсене, но преди нея можете да погледнете и Разделяй и Владей.

В тази секция задачите ще комбинират двоично търсене с някои от алгоритмите, които вече разгледахме - например итерация, алчен алгоритъм, графов алгоритъм, или проста структура данни. В секциите по-нататък ще видим задачи, в които двоичното търсене е комбинирано с по-сложни алгоритми (като например сложни структури данни, потоци, 2-SAT, хеширане, и други).