Реализуйте бинарный поиск: в отсортированном массиве найдите индекс целевого элемента или верните -1. Объясните, почему он работает и где ошибаются чаще всего.
Короткий ответ
- Работает только на отсортированных данных
- Сравниваем с серединой и отбрасываем половину
- Инвариант: ответ всегда внутри [lo, hi]
- Условие цикла lo <= hi, границы mid ± 1
- В языках с переполнением mid считают через lo + (hi - lo) / 2
- Вариации: левая граница, правая граница, поиск по ответу
Бинарный поиск отбрасывает половину диапазона на каждом шаге и работает за O(log n) по времени и O(1) по памяти.
Как сказать вслух
пример ответаЯ держу границы lo и hi, внутри которых гарантированно лежит ответ, если он есть. Сравниваю target с серединой и сдвигаю одну из границ за mid, чтобы диапазон строго уменьшался. Главное — аккуратность с условием цикла и плюс-минус единицей, здесь и живут все off-by-one ошибки.
Подробный ответ
Основной ответ
Границы lo = 0, hi = n - 1 задают отрезок-кандидат. Пока lo <= hi: берём mid, если a[mid] == target — нашли; если a[mid] < target — ответ правее, lo = mid + 1; иначе hi = mid - 1. Сдвиг именно за mid обязателен: mid уже проверен, и без исключения его из диапазона цикл зацикливается на двух элементах. Корректность держится на инварианте «target, если существует, лежит в [lo, hi]» — каждое сравнение его сохраняет. Сложность O(log n): диапазон делится пополам. В Python переполнения нет, но стоит упомянуть классический баг (lo + hi) в языках с фиксированными типами и запись lo + (hi - lo) // 2. Вариации с границами (первое вхождение, последнее, bisect_left) требуют другой пары условий — их стоит отрепетировать отдельно.
Ключевые моменты
- Инвариант. «Ответ внутри [lo, hi]» — формулировка, которая мгновенно отвечает на вопросы «почему <= в цикле» и «почему mid ± 1».
- Off-by-one. Либо lo <= hi с границами mid ± 1, либо lo < hi с hi = mid — смешение двух стилей даёт зацикливание или пропуск элемента.
- Переполнение. В Java/C++ (lo + hi) / 2 переполняется на больших индексах; пишут lo + (hi - lo) / 2.
- Поиск по ответу. Бинарный поиск применим к любой монотонной функции: минимальная скорость, вместимость, порог — ищем границу перехода false → true.
Практический контекст
Интервьюер проверяет не знание идеи — её знают все, — а способность написать без ошибок с первого раза и обосновать каждую деталь инвариантом. Протестируйте вслух края: пустой массив, один элемент, target меньше всех и больше всех, дубликаты. Будьте готовы к задачам-обёрткам: поиск в повёрнутом массиве, первое плохое билд-число, квадратный корень.
Пример кода
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi: # инвариант: target в a[lo..hi], если есть
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
a = [1, 3, 5, 7, 9, 11]
assert binary_search(a, 7) == 3
assert binary_search(a, 1) == 0
assert binary_search(a, 11) == 5
assert binary_search(a, 4) == -1
assert binary_search([], 1) == -1Частые ошибки
- Пишут lo = mid вместо mid + 1 и зацикливаются на диапазоне из двух элементов
- Путают условия lo < hi и lo <= hi между двумя стилями реализации
- Применяют бинарный поиск к неотсортированным данным или не проверяют предусловие