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

Если изначально у нас 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)).

Объясните, почему сложность бинарного поиска выражается через логарифм времени выполнения.