Зачем нужна ещё одна статья про бинарный поиск?

Как правило, обучающие материалы сводятся к показу одного «правильного» решения. Такие решения можно попробовать запомнить, но они быстро забываются и не помогают по-настоящему понять алгоритм.

Меня интригует вопрос: возможно ли объяснение, которое позволит не просто заучивать формулы, а понять саму логику? И если такое объяснение существует, даст ли оно возможность решать похожие задачи — или даже помогает становиться лучшим программистом?

Сразу оговорюсь: мы не будем останавливаться на тривиальных проверках,
вроде пустого массива или некорректных параметров. Фокус статьи — на сути алгоритма.

В этой статье мы не просто посмотрим на готовый код. Вместо этого мы:

1. Разберем ключевую идею алгоритма на простом примере.

2. Сконцентрируемся на крайнем случае, в котором ошибается большинство.

3. Сравним два подхода к реализации — с закрытым и полуоткрытым диапазоном.

4. Увидим, как небольшие изменения в коде позволяют решать целый класс задач.

Чтобы дальнейшее объяснение было предметным, в последующих примерах я буду использовать конкретный массив, отсортированный по неубыванию, и искомое значение:

const arr = [2, 7, 8, 11, 15, 29, 31];
const target = 30;

Ключевая идея бинарного поиска

Я не буду слишком подробно останавливаться на основной логике бинарного поиска. Почти каждая первая статья демонстрирует её с красивыми визуализациями. В этой статье я хочу сделать акцент на ключевом крайнем случае, разбор которого, по моей задумке, позволит не запоминать, а понять реализацию.

1) У нас есть отсортированный по неубыванию массив arr и искомое значение target.

2) Определим два указателя: left и right. В left запишем крайний левый индекс, в right — крайний правый:

let left = 0;
let right = arr.length - 1;

3) Вычислим mid — индекс, который находится посередине между left и right:

const mid = Math.floor((right + left) / 2)

Получив индекс mid, мы можем взять соответствующее значение из массива и сравнить его с target. Благодаря тому, что массив отсортирован, мы сразу можем понять, находится ли target левее или правее значения arr[mid]:

if (target === arr[mid]) {
  // нашли target, возвращаем индекс
} else if (target > arr[mid]) {
  // target больше arr[mid] — значит он в правой половине
} else {
  // target меньше arr[mid] — значит он в левой половине
}

4) Мы определили, в какой половине массива находится нужный элемент, а значит можем отбросить другую половину и продолжить поиск только в оставшейся. Таким образом, за одну операцию мы сокращаем диапазон поиска вдвое.

В бинарном поиске мы повторяем эту последовательность действий, на каждом шаге уменьшая диапазон, пока не найдём искомое значение или пока указатели left и right не пересекутся — это означает, что target в массиве не существует.

Классическое решение

Существует несколько вариантов реализации бинарного поиска. Сейчас мы познакомимся с классическим решением с "закрытым интервалом", которое чаще всего встречается в статьях и разборах.

Это решение, на мой взгляд, наиболее понятно для тех, кто только знакомится с бинарным поиском: упрощённое вычисление mid, и при сужении диапазона — для right вычитаем единицу, для left прибавляем.

export function binarySearchClosedInterval(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (target === arr[mid]) {
      return mid;
    } else if (target < arr[mid]) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
    }
  return -1;
}

Как видите, эта реализация полностью соответствует логике, которую я описал в начале статьи. Но именно здесь появляются детали, которые, хотя и можно заучить, гораздо лучше — понять.

Ключевой крайний случай

Я утверждаю, что понимание крайнего случая, который мы разберём в этом разделе, упростит для вас «написание» логики бинарного поиска в любой задаче и позволит не заучивать детали, в которых ошибаются 90% программистов.

Вернёмся к базовой логике бинарного поиска:

1. Создаём указатели left и right

2. Вычисляем средний индекс mid

3. Сравниваем искомое значение с arr[mid]. Если target больше — берём правую половину массива, если меньше — левую.

Критичный для понимания крайний случай возникает на шагах 2 и 3. Он заключается в том, что при двух соседних индексах формула расчёта mid возвращает меньший из них, и без «вспомогательного сдвига» указатели не смогут пересечься.

Пример: предположим, что left = 5, right = 6. Тогда mid = Math.floor((5 + 6) / 2) даст 5.

Небольшая справка: существует несколько формул для вычисления mid, но этот крайний случай актуален для всех. (Про "расширенную" формулу я расскажу отдельно — пока продолжаем на примере из начала статьи).

Давайте предметно посмотрим, как бинарный поиск ломается, если при обработке соседних индексов не делать "вспомогательный сдвиг".

Чтобы это показать, заменим корректный код на ошибочный:

// ПРАВИЛЬНЫЙ КОД
 } else if (target < arr[mid]) {
   right = mid - 1;
 } else {
   left = mid + 1;
 }

// НЕПРАВИЛЬНЫЙ КОД
 } else if (target < arr[mid]) {
   right = mid;
 } else {
   left = mid;
 }

Теперь подставим ошибочный код в функцию бинарного поиска и посмотрим, что произойдёт:

export function binarySearchWithError(
  arr = [2, 7, 8, 11, 15, 29, 31],
  target = 30
) {
  let left = 5;
  let right = 6;

  while (left <= right) { // true
    const mid = Math.floor((left + right) / 2); // 5
    if (target === arr[mid]) { // false
      return mid;
    } else if (target < arr[mid]) {
      right = mid;
    } else { // true
      left = mid; // 5
    }
  }
  return -1;
}

На следующей итерации указатели останутся теми же: [left, right] = [5, 6]. mid снова будет равен 5, и цикл никогда не завершится — он стал бесконечным.

Обратите внимание: неважно, какая из границ не сдвигается — даже если left и right в какой-то момент равны (например, [5, 5]), но mid всё ещё равен 5, ситуация останется тупиковой — и снова бесконечный цикл.

Эта ошибка решается добавлением вспомогательного сдвига на единицу:

 } else if (target < arr[mid]) {
   right = mid - 1;
 } else {
   left = mid + 1;
 }

ВЫВОДЫ:

Бинарный поиск должен сужаться на каждой итерации. Это работает, пока поиск не упирается в сравнение двух соседних индексов.

В этом крайнем случае важно понимать, что mid равен left, и нельзя повторно присваивать left = mid или right = mid — иначе диапазон не изменится, и цикл станет бесконечным.

Можно взглянуть на это иначе: когда мы сдвигаем границы на единицу, мы просто исключаем из диапазона индекс mid, который уже был проверен. Нет никакой причины оставлять его в следующей итерации.

Закрытый и полуоткрытый диапазоны

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

Прежде чем идти дальше, хочу зафиксировать две мысли:

1. Тема диапазонов шире, чем бинарный поиск. В этой статье я не ставлю задачу рассказать теорию или историю диапазонов — я хочу дать практическую информацию в контексте бинарного поиска. Если тема интересна глубже, рекомендую начать со статьи Эдсгера Дейкстры «Почему нумерация должна начинаться с нуля».

2. Существует отдельный термин — «ошибка на единицу» (off‑by‑one error). Он описывает типичные ошибки в циклах, когда количество итераций оказывается на единицу больше или меньше, чем нужно. Бесконечный цикл, который мы разобрали выше, — это классический пример ошибки на единицу. И я посмею предположить, что одна из главных её причин — неосознанный выбор типа диапазона.

Простой цикл с закрытым диапазоном

Диапазон определяет, какие значения индексов будут участвовать в итерации.

В случае закрытого диапазона:

for (let i = 0; i <= arr.length - 1; i++) {}

Особенности:

1. Начальная (0) и конечная (arr.length - 1) границы включаются.

2. Используется условие i <= ..., чтобы не пропустить последний элемент.

3. «Визитная карточка» — необходимость вычитать 1 из длины массива при задании правой границы. Именно этот -1 часто считают источником потенциальных ошибок.

Простой цикл с полуоткрытым диапазоном

Это более современный и идиоматичный подход, особенно в JavaScript (вспомните .slice(start, end)).

for (let i = 0; i < arr.length; i++) {}

1. Начальная точка (0) является ВКЛЮЧИТЕЛЬНОЙ, а конечная (arr.length) — ИСКЛЮЧИТЕЛЬНОЙ.

2. Поэтому в условии цикла мы используем оператор строгого сравнения <. Цикл остановится, как только итератор достигнет конечной, не-включительной точки.

3. «Визитная карточка» этого подхода — использование «чистой» длины массива (arr.length) в качестве конечной точки. Здесь нет никаких -1, что делает код чище и интуитивнее.

Бинарный поиск полуоткрытым диапазоном

Теперь посмотрим на бинарный поиск, реализованный через полуоткрытый диапазон:

function binarySearchHalfOpenInterval(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (target > arr[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  if (left === arr.length || arr[left] !== target) return -1;
  else return left;
}

В соответствии с элементарным примером полуоткрытого цикла, мы видим, что в данной реализации бинарного поиска начальная точка интервала всегда является ВКЛЮЧИТЕЛЬНОЙ, а конечная — ИСКЛЮЧИТЕЛЬНОЙ.

На практике это означает, что нам не нужно помнить о том, чтобы при обновлении правой границы вычитать единицу. Крайний правый индекс по умолчанию недостижим — он исключён из диапазона самим условием цикла while (left < right).

if (target > arr[mid]) {
   left = mid + 1;
} else {
   right = mid;
}

Другая важная особенность данной реализации в том, что мы напрямую не сравниваем arr[mid] с target. Мы возвращаем left, которое в конечном счёте, благодаря условию left = mid + 1, будет индексом элемента, у которого слева лежат все значения, строго меньшие target. Следовательно, само значение по индексу left является первым элементом, равным или большим target.

Эта особенность делает реализацию универсальной: она сразу решает несколько популярных задач, основанных на бинарном поиске. Например, задача findLeftBoundary / Find First Occurrence / lower_bound.

function findLeftBoundry(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (target > arr[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  if (left === arr.length) return -1;
  else return left;
}

А если немного изменить условие и вернуть left - 1, получим решение задачи findRightBoundary / Find Last Occurrence / upper_bound:

function findRightBoundry(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (target >= arr[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left - 1;
}

Бинарный поиск закрытым диапазоном (снова)

Классическое решение поиска полуоткрытым диапазоном отличается от классической реализации закрытым диапазоном. Интересно, и вы могли это заметить, но разница заключается не только в самих диапазонах.

В реализации с полуоткрытым диапазоном поиск продолжается, пока все значения, строго меньшие target, не окажутся слева:

 if (target > arr[mid]) {
   left = mid + 1;
 } else {
   right = mid;
 }

А в классической (и самой популярной!) реализации с закрытым диапазоном сравнение arr[mid] === target выполняется сразу, и при совпадении индекс немедленно возвращается:

 if (target === arr[mid]) {
   return mid;
 } else if (target > arr[mid]) {
   left = mid + 1;
 } else {
   right = mid - 1;
}

Следовательно, одна из финальных мыслей этой статьи в том, что реализация бинарного поиска с закрытым и полуоткрытым диапазоном различается не только формально — диапазонами, но и подходом к самой логике поиска.

Мы вполне можем написать реализацию с закрытым диапазоном, которая будет работать по принципу полуоткрытого варианта — без немедленного возврата, просто сужая диапазон до нужной точки.

function findLeftBoundryClosedInterval(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (target > arr[mid]) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  if (left < arr.length && arr[left] === target) {
    return left;
  }

  return -1;
}

Баг с переполнением

Вычисление mid кажется простой арифметикой, но есть нюанс: выражение (left + right) / 2 может переполниться в языках с фиксированным целым типом. В результате mid окажется неверным, и алгоритм поведёт себя непредсказуемо.

Чтобы этого избежать, используют более безопасную форму:

const mid = left + Math.floor((right - left) / 2);

Почему это безопасно:

1. right — left никогда не превышает длину диапазона; пока right>= left , разность не переполнит тип.

2. Далее прибавляем половину этой разности к left — итог всегда остаётся в пределах допустимых индексов.