5 классических ловушек при реализации бинарного поиска

Бинарный поиск — алгоритм, который все считают простым. Но именно в нём разработчики (включая опытных!) чаще всего делают незаметные ошибки, которые проявляются только при граничных случаях.​


📌 В этой статье:
  • Разберём типичные баги
  • Покажем примеры на C и Python
  • Поймём, почему в алгоритме «из трёх строк» столько нюансов

❶ Переполнение при вычислении середины в C​


C: 
// ⚠️ Ошибочный способ:
int mid = (left + right) / 2;

Если left и right большие (например, 2 000 000 000), произойдёт переполнение int, и mid станет отрицательным. Это сложно отследить.

✅ Безопасная версия:

C: 
int mid = left + (right - left) / 2;

➡️ Это работает корректно, даже если числа близки к INT_MAX.

🐍 В Python этого бага нет:

Python: 
mid = (left + right) // 2  # безопасно


❷ Бесконечный цикл при неправильно сдвинутых границах​


Если забыть сдвигать left или right, можно застрять в бесконечном цикле.

Python: 
# ⚠️ Пример ошибки
while left < right:
    mid = (left + right) // 2
    if arr[mid] < target:
        left = mid  # ❌ не left + 1!
    else:
        right = mid

✅ Нужно обязательно менять границы:

Python: 
left = mid + 1  # если текущая середина точно меньше цели

⛔ Если не сдвинуть left, цикл может не завершиться.


❸ Потеря значения при поиске первого/последнего вхождения​


Если в массиве несколько одинаковых элементов, обычный бинарный поиск вернёт любой, но не обязательно первый.

✅ Нужно немного модифицировать алгоритм (Алгоритм называется lower_bound и ищет первое вхождение):

Python: 
 left, right = 0, len(arr)
# Поиск первого вхождения
while left < right:
    mid = (left + right) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid

После цикла left будет указывать на первый индекс, где встречается значение target.

Обратите внимание на отличие от binary_search, тут right = len(arr), а не len(arr) - 1, а также while left < right.

Это важно т.к.:

binary_search использует закрытый интервал [left, right].
  • Оба конца включены.
  • Проверка: while (left <= right)
  • Подходит для поиска конкретного значения.

lower_bound использует полуоткрытый интервал [left, right)
  • Правая граница не входит в диапазон.
  • Проверка: while (left < right)
  • Это позволяет корректно обрабатывать случай, когда элемент должен быть вставлен в конец массива.


❹ Выход за границы массива​


Иногда встречается следующая ошибка:

C: 
// ❌ доступ к arr[mid + 1] без проверки
if (arr[mid + 1] == target) { ... }

Если mid == size - 1, произойдёт выход за границы. Это undefined behavior и может привести к крашу или ошибкам только на определённых входах.

✅ Всегда проверяй, что индекс не превышает размер массива:

C: 
if (mid + 1 < size && arr[mid + 1] == target)


❺ Неверное условие остановки цикла​


Частая ошибка — неправильное условие while.

Python: 
# ⚠️ Нестабильный вариант
while left <= right:
    ...

Это работает, но может быть трудно понять, что происходит на последних шагах.

✅ Альтернатива с left < right и сохранением инварианта:

Python: 
while left < right:
    ...

Подход left < right часто используют для поиска границ, особенно в задачах на бинарный поиск по функции (Binary Search on Answer).


📎 Вывод​

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

✅ Советуем: выписать реализацию вручную и проверять каждый шаг для всех граничных случаев.


💬 Какие баги в бинарном поиске ловили вы? Делитесь историями — особенно, если баг проявился уже в продакшене!