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

4. Search Insert Position

«Вставка элемента в упорядоченную структуру — это поиск места, где он должен был находиться с самого начала».
— Никлаус Вирт

В предыдущей статье 3. Binary Search мы разобрали классический бинарный поиск (Exact Match), который отвечает на строгий вопрос: «Присутствует ли заданное число в массиве?».

Но в системном программировании, при разработке B-Tree индексов в СУБД (PostgreSQL, SQLite), при поддержке упорядоченных in-memory структур (Log-Structured Merge-trees в RocksDB/Pebble) или в стандартной библиотеке Go (slices.BinarySearch), инженера чаще интересует другой вопрос: «Если элемента нет в массиве, то в какую позицию его необходимо поместить, чтобы сохранить сортировку?».

Задача Search Insert Position (LeetCode 35) — это канонический пример фундаментального паттерна Lower Bound (поиск нижней границы). Это строгая база, на которой строится поиск по ответу и навигация в структурах данных ядра.

Архитектура: Инвариант Lower Bound против Exact Match

В классическом поиске точного совпадения (Exact Match) мы использовали закрытый интервал [0, len(nums)-1] и три ветки: < target, > target и == target. При совпадении мы немедленно завершали работу (return mid).

В поиске позиции вставки (Lower Bound) архитектура меняется:

  1. Мы ищем первый индекс $i$, для которого nums[i] >= target: Если точный элемент найден, мы не имеем права выходить досрочно, если массив может содержать дубликаты — вставка обязана происходить перед первым дубликатом (требование стабильности порядка).
  2. Полуинтервал [0, len(nums)): Верхняя граница right инициализируется значением len(nums), а не len(nums) - 1. Если target больше любого элемента в срезе, его законная позиция для вставки — в самый конец, то есть на индекс len(nums).
  3. Безусловная сходимость: Условие цикла left < right гарантирует, что полуинтервал схлопывается в единственную точку left == right, которая и является искомой позицией.
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

    Start["Старт: nums = [1, 3, 5, 6], target = 2<br>left = 0, right = 4"]:::entry --> Check{"nums[mid] >= target?"}:::warning

    Check -->|"Да (3 >= 2)<br>Кандидат найден"| GoLeft["right = mid<br>Ищем левее, не теряя mid"]:::process
    Check -->|"Нет (1 < 2)<br>Слишком мало"| GoRight["left = mid + 1<br>Ответ строго правее"]:::process

    GoLeft --> Loop{"left < right?"}:::warning
    GoRight --> Loop
    Loop -->|"Да"| Check
    Loop -->|"Нет (left == right == 1)"| End["Возврат left = 1<br>Позиция для вставки числа 2"]:::success

Идиоматичная реализация на Go

Этот шаблон полуинтервала [left, right) — золотой стандарт конкурентного и системного программирования. Он полностью исключает ошибки выхода за границы среза и неоднозначности выхода из цикла.

Go 
package main

// searchInsert возвращает индекс элемента, если он найден в отсортированном срезе.
// Если элемент отсутствует, возвращается индекс, куда его следует вставить
// с сохранением порядка сортировки (паттерн Lower Bound).
// Временная сложность: O(log N)
// Пространственная сложность: O(1)
func searchInsert(nums []int, target int) int {
    // right инициализируется длиной среза: возможная позиция вставки в конец
    left, right := 0, len(nums)

    // Цикл сужает полуинтервал [left, right) до тех пор, пока left != right
    for left < right {
        // Защищенное от переполнения деление сдвигом в регистре CPU
        mid := int(uint(left+right) >> 1)

        if nums[mid] >= target {
            // Текущий элемент подходит или больше искомого:
            // ответ может быть в позиции mid или левее.
            // Сдвигаем правую границу, сохраняя mid в полуинтервале [left, mid).
            right = mid
        } else {
            // Элемент nums[mid] строго меньше target:
            // позиция вставки гарантированно находится правее.
            left = mid + 1
        }
    }

    // По выходу из цикла left == right — это точная позиция вставки
    return left
}

Взгляд под капот: Mechanical Sympathy

1. Предсказуемость ветвлений (Branch Prediction)

В цикле for left < right содержится всего одно бинарное условие (if ... else ...), в отличие от классического поиска с тремя исходами (<, >, ==).

  • Для аппаратного блока Branch Predictor в процессорах AMD Zen или Intel Core предсказание исхода двух ветвей на монотонных данных требует минимальных ресурсов.
  • Поскольку цикл не содержит досрочного выхода return mid, число итераций детерминировано и составляет строго $\lceil \log_2 (N+1) \rceil$. Это позволяет суперскалярному конвейеру процессора непрерывно спекулятивно вычислять инструкции без сбросов конвейера (Pipeline Flushes).

2. Доказанная безопасность Bounds Check (BCE)

Возникает резонный вопрос: если right = len(nums), не вызовет ли обращение nums[mid] панику рантайма runtime.panicIndex?

  • Формула mid := int(uint(left + right) >> 1) математически производит округление вниз.
  • Даже в худшем сценарии, когда left = len(nums) - 1 и right = len(nums), их полусумма дает mid = len(nums) - 1.
  • Значение mid строго меньше len(nums) на любой итерации цикла. Компилятор Go (cmd/compile) при включенной оптимизации доказывает данный инвариант и устраняет машинные инструкции проверки выхода за границы (CMPQ + JAE runtime.panicIndexOutBounds).

Подводные камни и вопросы с собеседований

Резюме

Search Insert Position демонстрирует мощь полуинтервального подхода [left, right):

  • right = len(nums) естественным образом включает индекс вставки за пределы массива.
  • nums[mid] >= target сжимает правую границу без потери кандидата.
  • Никаких скрытых аллокаций памяти — вычисления целиком происходят в регистрах процессора.

В следующей задаче мы абстрагируемся от физического массива в оперативной памяти и применим Lower Bound к динамическому интерфейсу поиска дефектов: 5. First Bad Version.