Какова временная сложность алгоритма бинарного поиска?

$O(\log n)$.

Бинарный поиск делит оставшийся диапазон пополам на каждой итерации, тем самым сокращая количество элементов, кот