Как работает бинарный поиск и какие у него граничные случаи?

Бинарный поиск работает на отсортированном массиве: каждый шаг отбрасывает половину диапазона, поэтому сложность O(log n); главные трудности — корректные границы и переполнение при вычислении середины.

Инвариант

Искомый элемент всегда лежит в полуинтервале [left, right). Пока диапазон не пуст, сравниваем середину с целью и сдвигаем границу:

const lowerBound = (a, target) => {
  let left = 0, right = a.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2); // защита от переполнения
    if (a[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
};

Типичные ошибки

• mid = (left + right) / 2 переполняется в языках с фиксированным int.
• Смешение [l, r] и [l, r) — бесконечные циклы и пропуск граничного элемента.
• Массив не отсортирован — результат не определён.

Обобщения

• Поиск первого или последнего вхождения, lower_bound и upper_bound.
• Бинарный поиск по ответу: если предикат монотонен («можно/нельзя»), ищем границу на числовой оси.

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

Бинарный поиск делит отсортированный диапазон пополам и находит элемент за O(log n). Главное — держать один инвариант границ, например [left, right): путаница с границами даёт бесконечный цикл, а на связном списке поиск бесполезен — нет доступа к середине.