Как настроить бинарный поиск: лайфхаки для безупречной реализации

Бинарный поиск — один из фундаментальных алгоритмов, который каждый программист изучает на заре своей карьеры. Его идея проста: найти элемент в отсортированном массиве за логарифмическое время O(log n). Однако за кажущейся простотой скрывается множество подводных камней, из-за которых даже опытные разработчики допускают ошибки, ведущие к бесконечным циклам или некорректным результатам. Правильная настройка границ, условий выхода и вычисления середины — вот три кита, на которых держится безупречный бинарный поиск. Давайте разберем лайфхаки, которые превратят его из потенциального источника багов в надежный инструмент.

Первый и главный лайфхак — **единообразие в определении границ**. Решите для себя, какой интервал представляет ваши границы `left` и `right`: *включающий* `[left, right]` или *полуоткрытый* `[left, right)`. От этого выбора зависит каждая строчка в цикле. Большинство ошибок происходит из-за смешения этих подходов. Рекомендуется использовать **полуоткрытый интервал** `[left, right)`, где `left` — индекс первого рассматриваемого элемента, а `right` — индекс, следующий за последним рассматриваемым. Почему? Это уменьшает вероятность ошибки на единицу (off-by-one) и упрощает логику.

Исходя из этого, инициализация будет: `left = 0`, `right = array.size`. Обратите внимание: `right` не является допустимым индексом массива. Цикл продолжается, пока в интервале есть хотя бы один элемент: `while (left < right)`. Когда `left == right`, интервал пуст `[x, x)` — поиск завершен.

Сердце алгоритма — вычисление середины. Классическая формула `(left + right) / 2` таит в себе риск переполнения для очень больших значений `left` и `right` (например, в 32-битных целых). Лайфхак: используйте безопасную формулу `left + (right - left) / 2`. Она математически эквивалентна, но исключает переполнение, так как вычитание происходит первым. В языках, где есть беззнаковые типы или большие целые, этой проблемой можно пренебречь, но привычка писать безопасный вариант — признак профессионализма.

Теперь самое тонкое — **обновление границ**. Здесь все зависит от того, что мы ищем: точное значение, первое вхождение или последнее. Допустим, мы ищем точное значение `target` в отсортированном массиве.

int binarySearch(int[] nums, int target) {
 int left = 0;
 int right = nums.length; // полуоткрытый интервал [left, right)
 while (left < right) {
 int mid = left + (right - left) / 2;
 if (nums[mid] == target) {
 return mid; // элемент найден
 } else if (nums[mid] < target) {
 // Искомый элемент в правой половине. mid уже проверен, исключаем его.
 left = mid + 1; // новый интервал [mid + 1, right)
 } else {
 // nums[mid] > target. Искомый элемент в левой половине.
 // mid не является ответом, но right должно указывать на границу.
 right = mid; // новый интервал [left, mid)
 }
 }
 // Интервал пуст, элемент не найден
 return -1;
}

Ключевые моменты: при `nums[mid] < target` мы сдвигаем `left` на `mid + 1`, так как сам `mid` уже не интересен. При `nums[mid] > target` мы присваиваем `right = mid`, потому что в полуоткрытом интервале `right` — это исключительная граница. Элемент с индексом `mid` не подходит, и он становится новой границей `right`.

Но чаще в реальных задачах требуется найти не любое вхождение, а **первое** (lower bound) или **последнее** (upper bound). Например, найти индекс первого элемента, не меньшего `target` (левая граница вставки). Это классическая задача поиска левой границы.

int lowerBound(int[] nums, int target) {
 int left = 0;
 int right = nums.length;
 while (left < right) {
 int mid = left + (right - left) / 2;
 if (nums[mid] < target) {
 // mid меньше target, значит, все что левее (включая mid) — точно меньше.
 // Первый подходящий элемент правее.
 left = mid + 1;
 } else {
 // nums[mid] >= target.
 // mid — кандидат на ответ, но нужно проверить левее.
 // Сужаем правую границу, включая mid в интервал поиска.
 right = mid;
 }
 }
 // В left (или right, они равны) лежит индекс первого элемента >= target.
 // Если все элементы меньше target, left будет равен nums.length.
 return left;
}

Лайфхак здесь в условии: мы не прерываем поиск при нахождении равенства (`nums[mid] == target`), а продолжаем сужать правую границу (`right = mid`), «притягивая» ее к первому такому элементу. Аналогично строится поиск последнего вхождения (upper bound), где условие ветвления меняется на `if (nums[mid]