Паттерн: Бинарный поиск

Признак в условии

• вход отсортирован
• «минимальное значение, при котором …» - свойство монотонно
• требуется сложность лучше линейной

Два шаблона - выучить оба

Точное совпадение, включительные границы:

let lo = 0, hi = n - 1;
while (lo <= hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (a[mid] === target) return mid;
  if (a[mid] < target) lo = mid + 1;
  else hi = mid - 1;
}
return -1;

Левая граница, полуинтервал - им решается всё остальное, включая поиск по ответу:

let lo = 0, hi = n;             // hi за последним элементом
while (lo < hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (!ok(mid)) lo = mid + 1;   // mid точно не ответ
  else hi = mid;                // mid может быть ответом: не отбрасываем
}
return lo;

Поиск по ответу

Когда ответ - число из диапазона, а проверка «подходит ли» считается за O(n): скорость поедания бананов, минимальная вместимость корабля, максимальная длина отрезка. Диапазон [1, max], функция ok(x) монотонна - дальше второй шаблон.

Сложность

Время O(log n) или O(n log range) при поиске по ответу.

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

• смешивают шаблоны: while (lo < hi) с hi = mid - 1 теряет ответ
• hi = mid при while (lo <= hi) даёт бесконечный цикл
• (lo + hi) / 2 может переполниться в языках с 32-битными целыми (в JS не страшно, но спрашивают)
• на повёрнутом массиве строгое сравнение вместо нестрогого ломается на длине 2

Мнемоника

«Инвариант, середина, выбрасываем половину»

Не путать с

• Два указателя - бинарный поиск отбрасывает половину; указатели идут по всем элементам. Если ответ нельзя проверить за шаг, поиска по ответу нет
• Жадность - в поиске по ответу проверка «подходит ли X» часто сама жадная - это не другой паттерн, а его часть

Задачи на этот паттерн

• Бинарный поиск
• Левая граница
• Поиск в повёрнутом массиве
• Минимум в повёрнутом массиве
• Бинарный поиск по ответу
• Поиск в отсортированной матрице
• Позиция вставки
• Любой локальный максимум
• Целочисленный корень

Суть

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

Как распознать по условию

• массив отсортирован, нужно найти элемент, позицию вставки, первое или последнее вхождение;
• «повёрнутый отсортированный массив», «пиковый элемент»;
• «минимальная скорость / вместимость / время, при которой получится»: бинпоиск по ответу;
• ограничения вида n до 10⁵ и значения до 10⁹ с требованием быстрее O(n · значение).

Один надёжный шаблон

Ищем первый индекс, где условие истинно, на полуинтервале [l, r):

function lowerBound(arr, x) {
  let l = 0, r = arr.length;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (arr[mid] >= x) r = mid;   // mid может быть ответом
    else l = mid + 1;             // mid точно не ответ
  }
  return l; // от 0 до arr.length
}

Через него выражается всё:

• есть ли x: i < n && arr[i] === x;
• первое вхождение: lowerBound(x);
• последнее вхождение: lowerBound(x + 1) - 1 для целых;
• позиция вставки: сам lowerBound.

Бинпоиск по ответу

function minSpeed(piles, h) {
  const can = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h;
  let l = 1, r = Math.max(...piles);
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (can(mid)) r = mid; else l = mid + 1;
  }
  return l;
}

Сложность: O(n · log max). Math.max(...piles) на очень больших массивах может упереться в лимит аргументов, тогда считай циклом.

Повёрнутый массив

На каждом шаге одна половина отсортирована (arr[l] <= arr[mid] значит левая). Проверяем, лежит ли x в отсортированной половине, и идём туда или в другую.

Ловушки

• l = mid при mid = (l + r) >> 1: вечный цикл на двух элементах.
• Смешивать [l, r] и [l, r): отсюда r = n против r = n - 1 и < против <=.
• >> на числах больше 2³¹: используй Math.floor.
• Бинпоиск по немонотонному условию.

Что спросят на собесе

• Напиши бинпоиск и объясни, почему он не зациклится.
• Как найти первое и последнее вхождение?
• Найди элемент в повёрнутом массиве.
• Что такое бинпоиск по ответу? Пример задачи.