Бинарный поиск элемента и границы без off-by-one

В предыдущих уроках мы работали со скользящим окном — двумя указателями, которые движутся в одну сторону и сужают или расширяют активный диапазон. Бинарный поиск устроен иначе: два указателя движутся навстречу, и на каждом шаге активный диапазон сжимается вдвое. Управлять этим диапазоном точно — вот главная задача урока.

Инвариант полуоткрытого отрезка [lo, hi) и его роль в бинарном поиске

Бинарный поиск — алгоритм, который на каждом шаге уменьшает область неизвестности вдвое. Чтобы это работало корректно при любых входных данных, нужно точно договориться: что именно означают две границы lo и hi в каждый момент выполнения.

Далее предполагается, что arr отсортирован по неубыванию. Только тогда из arr[mid] < target следует, что все позиции до mid тоже слишком малы, а из arr[mid] > target — что позиции от mid и правее слишком велики. Без сортировки отбрасывать половину области по одному сравнению нельзя.

Соглашение такое: область поиска — это полуоткрытый отрезок [lo, hi). Индекс lo входит в область, индекс hi — нет. Это значит, что активные кандидаты — индексы lo, lo+1, ..., hi-1, а их количество равно hi - lo.

Инициализация естественна для Python: lo = 0, hi = len(arr). Отрезок [0, len(arr)) охватывает весь массив — ни один элемент не потерян с самого начала.

Цикл выполняется пока lo < hi. Когда lo == hi, длина области равна нулю — активных кандидатов нет. Это единственное, что означает условие lo == hi: пустая область поиска. Что делать дальше — вернуть индекс или -1 — зависит не от самого инварианта, а от контракта конкретной функции.

Почему не [lo, hi] с включёнными обоими концами? Такое соглашение тоже работает, но в нём граничные случаи записываются менее однородно: пустая область — это lo > hi, что уже не так симметрично, а инициализация правого конца требует len(arr) - 1 с явным вычитанием единицы. Полуоткрытое соглашение [lo, hi) убирает этот специальный случай: длина области — всегда просто hi - lo, и когда она падает до нуля, цикл останавливается сам.

Инвариант обязан быть истинным перед каждой итерацией и после неё. Здесь оно звучит так: если искомый ответ существует, он находится внутри [lo, hi). Каждое обновление границ обязано это утверждение сохранять — иначе алгоритм может пропустить правильный ответ.

Вычисление mid и правила обновления границ без off-by-one

Есть два кандидата на вычисление середины:

mid = (lo + hi) // 2        # вариант A
mid = lo + (hi - lo) // 2  # вариант B

В Python оба дают одинаковый результат, потому что целые числа здесь неограниченны. Но вариант B — стандарт: в языках с фиксированной разрядностью (C, Java) lo + hi может переполниться, а lo + (hi - lo) — нет. Стоит писать вариант B сразу, чтобы не переучиваться.

При lo < hi выполняется lo ≤ mid < hi: индекс mid принадлежит текущей области и потому безопасен для чтения. Это гарантирует, что на каждом шаге хотя бы один элемент проверяется и область уменьшается.

После сравнения arr[mid] с целевым значением границы обновляются одним из двух способов:

• arr[mid] < target → ответ правее mid. Новая область: [mid+1, hi). Поэтому lo = mid + 1. Индекс mid исключён слева.
• arr[mid] > target → ответ левее mid. Новая область: [lo, mid). Поэтому hi = mid. Индекс mid исключён справа — и это бесплатно, потому что hi по соглашению не входит в область.

В обоих случаях инвариант [lo, hi) сохраняется: новые границы образуют строгое подмножество старой области, и mid в неё не входит.

В рамках выбранного инварианта нельзя заменить lo = mid + 1 на lo = mid: при hi = lo + 1 получим mid == lo, область не сузится и цикл зависнет. Замена hi = mid на hi = mid - 1 исключит без проверки индекс mid - 1, который может быть ответом. Именно эти две подмены либо нарушают инвариант, либо останавливают прогресс.

Точное значение, left_bound и right_bound

Три функции используют один и тот же каркас — инвариант [lo, hi) и формулу mid — но различаются условием обновления и тем, что делают с lo после выхода из цикла.

Поиск точного значения

def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

Здесь третья ветка появляется при равенстве — мы возвращаем mid немедленно, не доводя область до нуля. Если цикл завершился без возврата, lo == hi и область пуста: элемент не найден.

Есть нюанс: если в массиве несколько копий target, функция вернёт один из совпадающих индексов — не обязательно первый или последний. Когда это важно, нужны left_bound или right_bound.

Левая граница: первый индекс со значением ≥ target

def left_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid          # arr[mid] >= target: mid — кандидат, но может быть лучше левее
    # lo == hi; инвариант: все элементы до lo < target, все с lo и правее >= target
    if lo < len(arr) and arr[lo] == target:
        return lo
    return -1

Обратите внимание: ветка arr[mid] >= target сдвигает hi влево, но не исключает mid немедленно — он остаётся возможным ответом. Цикл продолжает сужать область, пока не найдёт самый левый подходящий индекс. После выхода lo указывает на первую позицию, где значение ≥ target. Финальная проверка arr[lo] == target отсеивает случай, когда target в массиве вообще нет.

Правая граница: последний индекс со значением = target

def right_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1      # mid <= target: ответ может быть правее или равен mid+1
        else:
            hi = mid
    # lo — первый индекс строго больше target
    if lo - 1 >= 0 and arr[lo - 1] == target:
        return lo - 1
    return -1

Здесь ветки поменялись: arr[mid] <= target двигает lo вправо. После выхода lo — первый индекс, где значение строго больше target (аналог upper_bound в стандартных библиотеках). Последний элемент, равный target, стоит ровно перед ним: lo - 1. Проверка arr[lo - 1] == target нужна на случай, если target не встречается вовсе.

Проверим ключевые свойства на примере:

arr = [1, 2, 4, 4, 4, 7, 9]
print(binary_search(arr, 4))  # один из индексов 2, 3 или 4
print(left_bound(arr, 4))     # 2
print(right_bound(arr, 4))    # 4
print(left_bound(arr, 5))     # -1
print(right_bound(arr, 5))    # -1

Для n > 0 число проверок в худшем случае не превышает ⌈log₂(n + 1)⌉; для пустого массива оно равно нулю. Если перед сравнением было m кандидатов и равенство не найдено, в новой области остаётся не более ⌊m / 2⌋ кандидатов.

Граничные случаи и типичные off-by-one ошибки при смешении схем

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

Пустой массив

При arr = [] инициализация даёт lo = 0, hi = 0. Условие lo < hi ложно сразу — цикл не выполняется. binary_search возвращает -1. left_bound: lo = 0, проверка 0 < 0 — ложь, возвращает -1. right_bound: lo = 0, lo - 1 = -1 < 0 — ложь, возвращает -1. Всё корректно без специальных проверок.

Один элемент

arr = [5], target = 5: lo = 0, hi = 1, mid = 0. binary_search сразу возвращает 0. left_bound: arr[0] >= 5, hi = 0, цикл заканчивается, arr[0] == 5 → возвращает 0. right_bound: arr[0] <= 5, lo = 1, цикл заканчивается, arr[0] == 5 → возвращает 0.

arr = [5], target = 3: binary_search — arr[0] > 3, hi = 0, возвращает -1. left_bound — arr[0] >= 3, hi = 0, arr[0] = 5 ≠ 3 → -1. right_bound — arr[0] > 3, hi = 0, lo = 0, lo - 1 = -1 < 0 → -1.

Все элементы одинаковы

arr = [4, 4, 4, 4]: left_bound(arr, 4) → 0, right_bound(arr, 4) → 3. binary_search вернёт какой-то внутренний индекс в зависимости от траектории.

---

Ошибка 1: lo = mid вместо lo = mid + 1

Для arr = [1, 3], target = 3 корректная ветка выглядит так:

lo=0, hi=2, mid=1, arr[1]=3  → должно быть lo = mid+1 = 2, выход

Но если написать lo = mid:

lo=0, hi=2, mid=1, arr[1]=3  → lo = 1
lo=1, hi=2, mid=1, arr[1]=3  → lo = 1  # бесконечный цикл

При hi = lo + 1 получаем mid = lo. Если ветка обновляет lo = mid, длина области остаётся равной 1 — цикл зависает.

Ошибка 2: hi = mid - 1 вместо hi = mid

arr = [1, 2, 3], target = 1:

lo=0, hi=3, mid=1, arr[1]=2 > 1 → hi = mid = 1 (корректно)
lo=0, hi=1, mid=0, arr[0]=1 == 1 → return 0

Теперь с ошибкой hi = mid - 1:

lo=0, hi=3, mid=1, arr[1]=2 > 1 → hi = 0
lo=0, hi=0 → цикл не входит, return -1

Индекс mid=1 исключён правильно, но заодно исключён и mid-1=0, который и был ответом — он выпал за пределы области без проверки.

Ошибка 3: смешение схем

Полуоткрытая схема [lo, hi) требует while lo < hi и hi = mid. Закрытая [lo, hi] требует while lo <= hi и hi = mid - 1. Если взять условие цикла от одной схемы и обновления от другой:

# Полуоткрытые границы, но цикл закрытой схемы
lo, hi = 0, len(arr)  # hi = n, но со схемой [lo, hi] hi должно быть n-1
while lo <= hi:        # при hi = n зайдём за конец при первом же mid > len(arr)-1
    mid = lo + (hi - lo) // 2
    if arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1  # ошибочное обновление для полуоткрытой схемы

При первом заходе hi = len(arr), mid может оказаться равным len(arr) если lo дорастёт до него — arr[mid] вызовет IndexError. На коротких массивах дефект может не проявиться, но при target больше всех элементов выполнение стабильно доходит до недопустимого индекса.

Чтобы не смешивать контракты, выберите одну схему и придерживайтесь её во всех ветках. Полуоткрытая [lo, hi) с while lo < hi, lo = mid + 1, hi = mid — самодостаточная система, которую не нужно адаптировать под каждый новый случай.