Модуль 21 ⏱ ~17 мин чтения 📐 2 Mermaid диаграмм

1. Теория. Бинарный поиск

«Всякий раз, отбрасывая половину пространства поиска, мы делаем гигантский шаг к истине, сокращая вечность до считанных миллисекунд».
— Дональд Кнут

Экспоненциальное сокращение пространства поиска

Поиск элемента в отсортированном массиве за логарифмическое время $O(\log N)$ — классическая тема первого семестра Computer Science. Однако на технических собеседованиях уровня Middle+ и Senior интервьюеры редко просят написать тривиальный поиск числа. От инженера ждут виртуозного владения граничными условиями (Lower / Upper Bound), умения находить экстремумы в абстрактных пространствах решений и понимания физики выполнения инструкций на современных CPU.

Логарифмический масштаб — величайшая сила в алгоритмах. Если массив содержит $1\,000\,000\,000$ (миллиард) элементов:

  • Линейный поиск ($O(N)$) в худшем случае потребует миллиарда обращений к памяти (секунды работы CPU).
  • Бинарный поиск ($O(\log_2 N)$) гарантированно локализует элемент всего за 30 шагов (наносекунды).

Но за эту математическую мощь приходится платить прецизионной точностью: малейшая ошибка в границах или условии цикла превращает алгоритм либо в бесконечный цикл, либо в генератор ошибок off-by-one.

Архитектура алгоритма и три канонических шаблона

Суть бинарного поиска состоит в поддержании инварианта: целевое значение гарантированно лежит внутри активного отрезка [left, right]. На каждом шаге мы вычисляем середину mid и за счет монотонности отбрасываем ровно половину пространства поиска.

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc

    Start["Диапазон [left, right]"]:::entry --> CalcMid["mid = left + (right - left) / 2"]:::process
    CalcMid --> Check{"nums[mid] против target"}:::warning

    Check -->|"nums[mid] == target"| Found["Элемент найден!"]:::success
    Check -->|"nums[mid] < target"| RightHalf["Отбрасываем левую половину:<br>left = mid + 1"]:::process
    Check -->|"nums[mid] > target"| LeftHalf["Отбрасываем правую половину:<br>right = mid - 1"]:::process

    RightHalf --> LoopCheck{"left <= right?"}:::warning
    LeftHalf --> LoopCheck
    LoopCheck -->|"Да"| CalcMid
    LoopCheck -->|"Нет"| NotFound["Элемент отсутствует"]:::error

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

Шаблон 1: Точный поиск (Exact Match: left <= right)

Используется, когда нужно найти точное совпадение с target в массиве без повторяющихся элементов:

Go 
left, right := 0, len(nums)-1
for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
        return mid
    } else if nums[mid] < target {
        left = mid + 1
    } else {
        right = mid - 1
    }
}
return -1

Шаблон 2: Левая граница / Первое вхождение (Lower Bound: left < right)

Используется для поиска первого элемента, удовлетворяющего предикату (например, nums[i] >= target или isBadVersion(i)).
Инвариант: искомый ответ всегда находится в полуинтервале [left, right). При выходе из цикла left == right, поэтому гадать с возвращаемым индексом не нужно:

Go 
left, right := 0, len(nums) // right за пределами массива
for left < right {
    mid := left + (right-left)/2
    if nums[mid] >= target {
        right = mid     // mid может быть ответом, сохраняем его
    } else {
        left = mid + 1  // mid точно не подходит
    }
}
return left // Индекс первого элемента >= target

Шаблон 3: Окно из двух элементов (left + 1 < right)

Используется в сложных задачах, где для решения требуется сравнить текущий элемент с его непосредственными соседями nums[mid-1] и nums[mid+1] (например, поиск пика в массиве Find Peak Element). При выходе из цикла всегда остаются ровно два кандидата left и right, которые проверяются вручную.

Знаменитая ловушка: Целочисленное переполнение (Integer Overflow)

Самая известная ошибка в истории алгоритмического программирования, которая более 20 лет скрывалась в стандартной библиотеке Java Arrays.binarySearch, таится в невинной формуле:

Go 
mid := (left + right) / 2 // СКРЫТАЯ БОМБА!

Mechanical Sympathy: Почему процессор «не любит» бинарный поиск

Асимптотически бинарный поиск на миллионе элементов ($~20$ операций) сокрушает линейный поиск ($1\,000\,000$ операций).
Однако на интервью в финтех или HFT вам зададут провокационный вопрос:
«Какой поиск выполнится быстрее на отсортированном массиве из 32–64 чисел: линейный $O(N)$ или бинарный $O(\log N)$?»

Правильный ответ Senior-инженера: Линейный поиск будет физически быстрее бинарного на малых размерах данных.

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

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc

    subgraph LinearSearch["Линейный поиск: Идеальная локальность"]
        L1["nums[0]"]:::success --> L2["nums[1]"]:::success --> L3["nums[2]"]:::success
        Note1["Prefetcher заранее подкачивает 64B кэш-линии.<br>Branch Predictor угадывает 99% условий."]
    end

    subgraph BinarySearch["Бинарный поиск: Хаотичные прыжки"]
        B1["nums[32]"]:::process -.->|"Прыжок"| B2["nums[16]"]:::error -.->|"Прыжок"| B3["nums[24]"]:::error
        Note2["Каждый прыжок — промах кэша (Cache Miss).<br>Branch Predictor ошибается в 50% ветвлений (Stall)."]
    end
  1. Разрушение аппаратного префетчера (Hardware Prefetcher):
    Линейный скан читает память непрерывно. Контроллер памяти ядра загружает кэш-линии на опережение — данные всегда лежат в сверхбыстром L1d-кэше (1 такт). Бинарный поиск прыгает по адресам хаотично: idx = 32, затем 16, затем 24. Каждый прыжок выбивает процессор в ожидание системной шины RAM (до 100–200 тактов задержки).
  2. Ошибки предсказания ветвлений (Branch Misprediction):
    Условие if nums[mid] < target с вероятностью 50% истинно и 50% ложно. Процессорный блок Branch Target Buffer не может выявить закономерность и ошибается в половине случаев, вызывая сброс конвейера инструкций (Pipeline Flush) на 15–20 тактов.

Бинарный поиск в стандартной библиотеке Go: sort против slices

В языке Go есть два поколения инструментов для бинарного поиска:

Go 
// sort.Search принимает предикат func(int) bool
idx := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= target
})

Недостаток: Анонимная функция (замыкание) порождает накладные расходы на косвенный вызов через указатель функции на каждой итерации логарифмического цикла.

2. Современный стандарт (Go 1.21+): пакет slices

Go 
import "slices"

// Generic-поиск с возвратом точного индекса и флага нахождения
idx, found := slices.BinarySearch(nums, target)
if found {
    fmt.Printf("Найден по индексу: %d\n", idx)
} else {
    fmt.Printf("Не найден. Точка для вставки (Lower Bound): %d\n", idx)
}

Преимущество: Пакет slices построен на дженериках (cmp.Ordered). Компилятор Go инлайнит код поиска напрямую в машинные инструкции целевого типа без единой аллокации и оверхеда на замыкания (Monomorphization).

Итог

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

Переходим к одному из самых мощных алгоритмических приемов в реальном бэкенде: 2. Поиск по ответу.