Обяснете защо сложността на двоичното търсене се изразява чрез логаритъма на времето за изпълнение.

Бинарното търсене работи върху сортиран масив, като всеки път разделя областта за търсене на две. На всяка стъпка то изключва половината от останалите елементи, така че броят на елементите, които трябва да проверите, намалява в геометрична прогресия.

Ако първоначално имаме n елемента, след първата стъпка остават n/2, след това n/4, n/8 и така нататък, докато не остане само един елемент. Броят на тези деления е броят стъпки на алгоритъма и е равен на числото k, за което ( n / 2^k = 1 ).

Решавайки уравнението, получаваме:

[ 2^k = n \implies k = \log_2 n ]

Така времето за изпълнение на бинарното търсене е пропорционално на логаритъма на размера на входните данни, тоест (O(\log n)). Това е много по-ефективно от линейното търсене с (O(n)).