Binary Search и варианты

Бинарный поиск — это не просто “найти элемент в отсортированном массиве”, это фундаментальная парадигма: поиск по монотонному предикату через дихотомию. Если есть функция f(x), которая меняет значение с false на true (или наоборот) ровно один раз, бинарный поиск найдёт точку перехода за O(log n). Эта идея применяется везде: “минимальная скорость, при которой Коко съест все бананы за h часов”, “k-й элемент в матрице, отсортированной по строкам и столбцам”, “корень квадратный с точностью ε”, “минимальная ёмкость корабля для перевозки за D дней”. Шаблон один: оценить диапазон ответа [lo, hi], написать предикат can(mid) → boolean, бинарно искать минимальное (или максимальное) mid, для которого предикат истинен.

Классический бинарный поиск с инвариантом [lo, hi] (включительно с обеих сторон) работает так: mid = (lo + hi) / 2, если arr[mid] == target → нашли, если arr[mid] < target → lo = mid + 1 (ответ справа), иначе hi = mid - 1 (ответ слева). Цикл while (lo <= hi). Возвращаем -1, если не нашли. Но этот вариант имеет проблемы: (1) не работает для поиска “первого/последнего вхождения”, (2) легко сделать off-by-one ошибку, (3) переполнение при (lo + hi).

Когда применять / Мотивация

Идея / Как работает

Более надёжный подход: полуинтервал [lo, hi) — lo включён, hi не включён. Инвариант: ответ всегда в [lo, hi). Цикл while (lo < hi). mid = lo + (hi - lo) / 2. Если проверка не прошла → lo = mid + 1 (исключаем mid), если прошла → hi = mid (mid может быть ответом, оставляем в диапазоне). На выходе lo == hi — это ответ. Этот подход избегает большинства off-by-one ошибок и естественно работает для lower_bound (первый элемент ≥ target) и upper_bound (первый элемент > target).

Три канонических варианта: (1) Классический — ищем точное вхождение, [lo, hi], возвращаем индекс или -1. (2) Lower bound — первый индекс, где arr[i] ≥ target, [lo, hi), возвращаем lo (может быть == n, если все элементы < target). (3) Upper bound — первый индекс, где arr[i] > target, [lo, hi), возвращаем lo. Для диапазона вхождений: [lower_bound, upper_bound). Если lower_bound == upper_bound, элемента нет.

Binary search по ответу (самый мощный паттерн!): Когда задача звучит как “минимальное X, при котором возможно Y” или “максимальное X, при котором выполняется условие C”, и условие монотонно (если работает для X, то работает для всех X’ > X), используем бинарный поиск по X. Шаги: (1) Определить диапазон [lo, hi] для ответа. (2) Написать функцию can(mid) → boolean, проверяющую условие. (3) Бинарно искать минимальное mid, для которого can(mid) == true (или максимальное, для которого can(mid) == true, в зависимости от задачи). Примеры: Koko Eating Bananas (минимальная скорость поедания), Capacity To Ship Packages Within D Days (минимальная вместимость), Split Array Largest Sum (минимизация максимальной суммы подмассива).

Реализация

Задача: Find First and Last Position of Element in Sorted Array (LeetCode 34). Дан отсортированный массив nums и target, найти начальную и конечную позицию target. Если target не найден, вернуть [-1, -1]. Требуется O(log n).

Подход: Это классическая задача на lower_bound и upper_bound. (1) Найдём lower_bound — первый индекс i, где nums[i] >= target. (2) Проверим, что nums[lower_bound] == target (иначе элемента нет). (3) Найдём upper_bound — первый индекс j, где nums[j] > target. (4) Диапазон [lower_bound, upper_bound - 1]. Альтернативный подход: модифицировать бинарный поиск для поиска “первого” и “последнего” вхождения отдельно. Используем инвариант [lo, hi) для надёжности и отсутствия off-by-one ошибок.

function searchRange(nums, target) {
    const lowerBound = findBound(nums, target, true);
    if (lowerBound === nums.length || nums[lowerBound] !== target) {
      return [-1, -1]; // target не найден
    }
    const upperBound = findBound(nums, target, false);
    return [lowerBound, upperBound - 1];
  }

  function findBound(nums, target, isLower) {
    let lo = 0, hi = nums.length;

    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);

      if (nums[mid] > target || (isLower && nums[mid] === target)) {
        // Для lower: если нашли target, продолжаем искать слева
        // Для upper: если > target, ищем слева
        hi = mid;
      } else {
        // Для lower: если < target, ищем справа
        // Для upper: если <= target, ищем справа
        lo = mid + 1;
      }
    }

    return lo;
  }

  // Альтернативная реализация: отдельные функции
  function searchRangeAlt(nums, target) {
    const first = findFirst(nums, target);
    if (first === -1) return [-1, -1];
    const last = findLast(nums, target);
    return [first, last];
  }

  function findFirst(nums, target) {
    let lo = 0, hi = nums.length - 1;
    let result = -1;

    while (lo <= hi) {
      const mid = lo + Math.floor((hi - lo) / 2);

      if (nums[mid] === target) {
        result = mid;
        hi = mid - 1; // продолжаем искать слева
      } else if (nums[mid] < target) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    return result;
  }

  function findLast(nums, target) {
    let lo = 0, hi = nums.length - 1;
    let result = -1;

    while (lo <= hi) {
      const mid = lo + Math.floor((hi - lo) / 2);

      if (nums[mid] === target) {
        result = mid;
        lo = mid + 1; // продолжаем искать справа
      } else if (nums[mid] < target) {
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }

    return result;
  }

  // Binary search по ответу: Koko Eating Bananas (LeetCode 875)
  function minEatingSpeed(piles, h) {
    // Минимальная скорость k бананов/час, чтобы съесть все за h часов
    let lo = 1; // минимальная возможная скорость
    let hi = Math.max(...piles); // максимальная (съедаем самую большую кучу за 1 час)

    while (lo < hi) {
      const mid = lo + Math.floor((hi - lo) / 2);

      if (canFinish(piles, mid, h)) {
        hi = mid; // mid работает, пробуем меньше
      } else {
        lo = mid + 1; // mid не работает, нужно больше
      }
    }

    return lo;
  }

  function canFinish(piles, k, h) {
    let hours = 0;
    for (const pile of piles) {
      hours += Math.ceil(pile / k);
      if (hours > h) return false; // early exit
    }
    return hours <= h;
  }

  // Демонстрация
  console.log(searchRange([5,7,7,8,8,10], 8)); // [3, 4]
  console.log(searchRange([5,7,7,8,8,10], 6)); // [-1, -1]
  console.log(searchRange([], 0)); // [-1, -1]
  console.log(minEatingSpeed([3,6,7,11], 8)); // 4
  console.log(minEatingSpeed([30,11,23,4,20], 5)); // 30

Трассировка

Трассировка findBound([5,7,7,8,8,10], 8, true) — поиск lower bound:

  nums = [5,7,7,8,8,10], target = 8, isLower = true
  lo = 0, hi = 6 (длина массива)

  Итерация 1:
    mid = 0 + (6 - 0) / 2 = 3
    nums[3] = 8
    nums[mid] === target && isLower → hi = mid
    lo = 0, hi = 3

  Итерация 2:
    mid = 0 + (3 - 0) / 2 = 1
    nums[1] = 7
    nums[mid] < target → lo = mid + 1
    lo = 2, hi = 3

  Итерация 3:
    mid = 2 + (3 - 2) / 2 = 2
    nums[2] = 7
    nums[mid] < target → lo = mid + 1
    lo = 3, hi = 3

  lo == hi, выход из цикла
  Возвращаем lo = 3 (первое вхождение 8)

  Трассировка findBound([5,7,7,8,8,10], 8, false) — поиск upper bound:
  lo = 0, hi = 6

  Итерация 1:
    mid = 3
    nums[3] = 8
    nums[mid] <= target (не > target) → lo = mid + 1
    lo = 4, hi = 6

  Итерация 2:
    mid = 4 + (6 - 4) / 2 = 5
    nums[5] = 10
    nums[mid] > target → hi = mid
    lo = 4, hi = 5

  Итерация 3:
    mid = 4 + (5 - 4) / 2 = 4
    nums[4] = 8
    nums[mid] <= target → lo = mid + 1
    lo = 5, hi = 5

  lo == hi, выход
  Возвращаем lo = 5 (первый элемент > 8)

  Результат: [3, 5 - 1] = [3, 4]

  Трассировка minEatingSpeed([3,6,7,11], 8):
  lo = 1, hi = 11

  Итерация 1: mid = 6
    canFinish([3,6,7,11], 6, 8):
      pile 3: ceil(3/6) = 1 час
      pile 6: ceil(6/6) = 1 час
      pile 7: ceil(7/6) = 2 часа
      pile 11: ceil(11/6) = 2 часа
      total = 6 часов <= 8 → true
    hi = 6

  Итерация 2: lo=1, hi=6, mid=3
    canFinish([3,6,7,11], 3, 8):
      3: ceil(3/3)=1, 6: ceil(6/3)=2, 7: ceil(7/3)=3, 11: ceil(11/3)=4
      total=10 > 8 → false
    lo = 4

  Итерация 3: lo=4, hi=6, mid=5
    canFinish(5, 8):
      3: 1, 6: 2, 7: 2, 11: 3 → total=8 → true
    hi = 5

  Итерация 4: lo=4, hi=5, mid=4
    canFinish(4, 8):
      3: 1, 6: 2, 7: 2, 11: 3 → total=8 → true
    hi = 4

  lo == hi = 4, ответ: 4 банана/час

Сложность

Анализ сложности: Time: O(log n) для каждого вызова findBound, так как на каждой итерации диапазон сокращается вдвое, итераций log₂(n). searchRange делает два вызова → O(2 log n) = O(log n). minEatingSpeed: диапазон [1, max(piles)], пусть M = max(piles). Бинарный поиск делает log₂(M) итераций. Каждая итерация вызывает canFinish, который проходит по всем n кучам → O(n). Итого O(n log M). Space: O(1) дополнительной памяти (если не считать стек рекурсии, но все наши реализации итеративные). Альтернатива для searchRange — линейный проход от найденной позиции влево/вправо — даст O(n) в худшем случае (если все элементы равны target).

Частые ошибки на интервью: (1) Переполнение в mid = (lo + hi) / 2 при больших значениях (используй mid = lo + (hi - lo) / 2 или mid = lo + Math.floor((hi - lo) / 2) в JS). (2) Путаница в инварианте — когда использовать hi = mid, а когда hi = mid - 1. Правило: если исключаем mid как возможный ответ → lo = mid + 1 или hi = mid - 1; если оставляем mid в рассмотрении → hi = mid или lo = mid. (3) Если используешь lo = mid (не mid + 1), нужно брать mid = lo + Math.ceil((hi - lo) / 2), иначе бесконечный цикл при lo = hi - 1. (4) Забыть проверить граничные случаи: пустой массив, один элемент, target меньше всех, target больше всех. (5) В задачах с floating-point (sqrt(x)) — использовать while (hi - lo > ε) вместо lo < hi.

Типичные ошибки и подводные камни

(1) “Как искать в повёрнутом массиве?” — Search in Rotated Sorted Array: проверяем, какая половина отсортирована (nums[lo] <= nums[mid] → левая, иначе правая), затем проверяем, попадает ли target в отсортированную половину, если да — ищем там, иначе в другой. Одна модификация классического бинарного поиска. (2) “Что если массив может содержать дубликаты?” — В rotated array с дубликатами худший случай O(n), когда nums[lo] == nums[mid] == nums[hi] — не можем определить, где поворот, приходится линейно искать. (3) “Median of Two Sorted Arrays за O(log(min(m,n)))?” — Бинарный поиск по partition в меньшем массиве, поддерживая инвариант: левые части обоих массивов содержат ровно (m+n+1)/2 элементов, и max(left) <= min(right). (4) “Find Peak Element за O(log n)?” — На каждом шаге проверяем nums[mid] > nums[mid+1]: если да, peak слева (включая mid), иначе peak справа. Гарантия: nums[-1] = nums[n] = -∞. (5) “Переполнение в mid?” — В JS нет проблемы с integer overflow до Number.MAX_SAFE_INTEGER (2⁵³-1), но в Java/C++ нужно lo + (hi - lo) / 2 или lo + ((hi - lo) >> 1).

Follow-up вопросы интервьюера

Реализуй sqrt(x) с точностью ε через бинарный поиск. — lo = 0, hi = x (или x/2 для x >= 4), mid = lo + (hi - lo) / 2.0, while (hi - lo > ε) { if (mid * mid > x) hi = mid; else lo = mid; }. Возвращаем (lo + hi) / 2. Сложность O(log(x/ε)). Альтернатива: метод Ньютона (итерация x_new = (x + n/x) / 2) сходится за O(log log n) итераций, но требует понимания производных.
Capacity To Ship Packages Within D Days — объясни подход. — Бинарный поиск по capacity. lo = max(weights) (минимум — вес самого тяжёлого пакета), hi = sum(weights) (максимум — всё за один день). can(mid) проверяет: можем ли перевезти за D дней с вместимостью mid? Жадно складываем пакеты в текущий день, пока сумма <= mid, переходим к следующему дню. Если дней > D → false. Ищем минимальное mid, для которого can(mid) == true.
Kth Smallest Element in a Sorted Matrix — как за O(n log(max - min))? — Матрица n×n, каждая строка и столбец отсортированы. Бинарный поиск по значению (не по индексу!). lo = matrix[0][0], hi = matrix[n-1][n-1]. can(mid) считает количество элементов <= mid: для каждой строки идём справа налево, пока matrix[row][col] > mid, считаем количество. Если count >= k → hi = mid, иначе lo = mid + 1. Возвращаем lo.
Почему бинарный поиск не работает на несортированных данных? — Потому что монотонность нарушена: не можем сказать, в какой половине искать. Исключение: если есть другая монотонность (например, bitonic array — возрастает до пика, затем убывает, можно найти пик за O(log n), затем два бинарных поиска). Для несортированных данных — хеш-таблица O(1) или линейный поиск O(n).
Split Array Largest Sum — минимизируй максимальную сумму подмассива при разбиении на m частей. — Бинарный поиск по ответу (максимальной сумме). lo = max(nums), hi = sum(nums). can(mid, m) проверяет: можем ли разбить на m подмассивов так, чтобы каждый имел сумму <= mid? Жадно: текущая сумма += nums[i], если превысили mid → начинаем новый подмассив, увеличиваем счётчик. Если подмассивов > m → false. Ищем минимальное mid.
Как найти элемент в бесконечном отсортированном массиве? — Сначала найдём диапазон: стартуем с hi = 1, удваиваем hi, пока arr[hi] < target (экспоненциальный поиск). Это займёт O(log k) итераций, где k — позиция target. Затем обычный бинарный поиск в [hi/2, hi] за O(log k). Итого O(log k). Это эффективнее, чем линейный поиск диапазона за O(k).

Чеклист на собес

Использую закрытый интервал [l, r] или полуоткрытый [l, r) — чётко проговариваю инвариант.
mid = l + ((r - l) >> 1) — защита от переполнения и чуть быстрее, чем (l+r)/2 в JS Number.
Различаю lower_bound (первый ≥ target) и upper_bound (первый > target) — это разные шаблоны.
Условие выхода: l < r (поиск границы) или l <= r (точное совпадение). Не путаю.
Узнаю «binary search по ответу»: монотонная функция feasibility, дискретный или вещественный диапазон.
Для float-версии задаю эпсилон или фиксированное число итераций (~100).
Проверяю граничные случаи: пустой массив, target меньше всех, target больше всех, дубликаты.