Објасните зашто се сложеност бинарног претраживања изражава кроз логаритам времена извршења.

Бинарный поиск работает на отсортированном массиве, каждый раз деля область поиска пополам. На каждом шаге он исключает половину оставшихся элементов, поэтому количество элементов, которые нужно проверить, уменьшается в геометрической прогрессии.

Если изначально у нас n элементов, после первого шага остаётся n/2, затем n/4, n/8 и так далее, пока не останется 1 элемент. Количество таких делений — это количество шагов алгоритма, и оно равно числу k, при котором ( n / 2^k = 1 ).

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

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

Таким образом, время выполнения бинарного поиска пропорционально логарифму от размера входных данных, то есть (O(\log n)). Это гораздо эффективнее, чем линейный поиск с (O(n)).