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

Сложность бинарного поиска — O(log n) по времени. На каждом шаге диапазон поиска уменьшается вдвое.

Временная сложность: O(log n)

Бинарный поиск делит отсортированный массив пополам на каждом шаге, отбрасывая половину элементов. Число шагов — сколько раз n можно поделить на 2, то есть log₂(n).

n = 1 000 000 → ~20 шагов (log₂(1000000) ≈ 20)
n = 1 000 000 000 → ~30 шагов

Поэтому бинарный поиск чрезвычайно эффективен на больших данных.

Пространственная сложность

• Итеративная реализация — O(1) (только несколько переменных).
• Рекурсивная — O(log n) из-за стека вызовов.

Условие применимости

O(log n) достигается только на отсортированном массиве. Если данные не отсортированы, нужна предварительная сортировка O(n log n), что может нивелировать выгоду при разовом поиске.

Сравнение с линейным поиском

• Линейный — O(n): проверяет каждый элемент.
• Бинарный — O(log n): в разы быстрее на больших массивах.

Коротко для собеседования

Бинарный поиск — O(log n) по времени (диапазон делится пополам каждый шаг): для миллиона элементов ~20 шагов. Память O(1) итеративно, O(log n) рекурсивно. Требует отсортированного массива. Значительно быстрее линейного O(n).