Бинарный поиск: вариации

Вариации бинарного поиска (binary search variations) — адаптации классического алгоритма для поиска левой/правой границы диапазона, первого/последнего вхождения и ответа на монотонных функциях.

Зачем нужно

Классический бинарный поиск находит только один индекс элемента в отсортированном массиве. В реальных задачах чаще нужно найти первое/последнее вхождение дубликата, левую или правую границу диапазона, или минимальное значение, удовлетворяющее условию. Знание вариаций позволяет решать эти задачи за O(log n).

Где используется

  • Задачи LeetCode/CP: поиск границ, lower_bound / upper_bound
  • Базы данных: поиск диапазонов в индексах (B-tree range queries)
  • Поиск минимального/максимального значения параметра, удовлетворяющего условию (binary search on answer)
  • Array.prototype в C++ STL: lower_bound, upper_bound

Основной контент

1. Классический бинарный поиск

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

2. Lower bound — первый индекс ≥ target

Аналог std::lower_bound в C++. Возвращает позицию первого элемента не меньше target.

function lowerBound(arr, target) {
  let lo = 0, hi = arr.length; // hi = length (за правым краем)
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // lo === hi: первый индекс >= target
}

// [1, 2, 2, 3, 3, 5]
// lowerBound(arr, 3) → 3 (индекс первой тройки)
// lowerBound(arr, 4) → 5 (индекс, куда вставить 4)

3. Upper bound — первый индекс > target

function upperBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // первый индекс > target
}

// [1, 2, 2, 3, 3, 5]
// upperBound(arr, 3) → 5 (после последней тройки)
// Количество вхождений 3: upperBound - lowerBound = 5 - 3 = 2

4. Binary search on answer

Применяется когда ищем минимальное/максимальное значение x, при котором выполняется монотонное условие check(x).

// Пример: минимальная скорость, чтобы съесть n бананов за h часов (LeetCode 875)
function minEatingSpeed(piles, h) {
  function canFinish(speed) {
    return piles.reduce((sum, p) => sum + Math.ceil(p / speed), 0) <= h;
  }
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (canFinish(mid)) hi = mid; // можно медленнее?
    else lo = mid + 1;            // нужно быстрее
  }
  return lo;
}

Шаблон выбора варианта

Нужно...                        → Используй
Найти конкретный элемент        → Классический
Первый индекс >= target         → Lower bound
Первый индекс > target          → Upper bound  
Мин. x, при котором check(x)   → Binary search on answer (lo < hi, hi = mid)
Макс. x, при котором check(x)  → Binary search on answer (lo < hi, lo = mid+1)

Частые ошибки

  • Использовать hi = arr.length - 1 вместо hi = arr.length в lower/upper bound — тогда крайний элемент недоступен.
  • Условие lo <= hi вместо lo < hi в lower/upper bound — вызывает бесконечный цикл.
  • Не проверять, что условие действительно монотонно при binary search on answer.
  • Вычислять mid = (lo + hi) / 2 без >> 1 или Math.floor — в JS результат float.

Связанные темы

Ресурсы