6. Find Minimum in Rotated Sorted Array

«Даже если порядок нарушен, в структуре всегда остается след ее первоначальной гармонии».
— Брайан Керниган

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

Задача Find Minimum in Rotated Sorted Array (LeetCode 153) вводит важную модель: изначально отсортированный массив уникальных чисел был циклически сдвинут (повернут) неизвестное количество раз.
Например: массив [0, 1, 2, 4, 5, 6, 7] после поворота превращается в [4, 5, 6, 7, 0, 1, 2].

Необходимо найти минимальный элемент массива за логарифмическое время $O(\log N)$.

Архитектура: Геометрия двух восходящих отрезков

Если визуализировать значения повернутого массива в виде графика, мы увидим не единую прямую, а два параллельно восходящих отрезка, разделенных точкой разрыва (инфлексии):

$$\underbrace{[4, 5, 6, 7]}_{\text{Левый отрезок (высокий)}} \quad \big\downarrow \quad \underbrace{[0, 1, 2]}_{\text{Правый отрезок (низкий)}}$$

Минимальный элемент массива — это самая первая точка правого отрезка (абсолютное дно разрыва).

Ключевой архитектурный вопрос: с каким элементом сравнивать середину nums[mid]?
Сравнение необходимо проводить с правым краем nums[right]:

1. Если nums[mid] > nums[right]: mid гарантированно лежит на высоком (левом) отрезке. Вся зона от left до mid монотонно возрастает и заведомо больше любого элемента правого отрезка. Минимальный элемент находится строго справа. Сдвигаем: left = mid + 1.
2. Если nums[mid] < nums[right]: mid гарантированно лежит на низком (правом) отрезке. Поскольку этот отрезок также монотонно возрастает, минимальный элемент — это либо сам nums[mid], либо элемент, расположенный левее. Исключать mid нельзя: 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

    Start["Повернутый массив: [4, 5, 6, 7, 0, 1, 2]<br>left = 0, right = 6"]:::entry --> Check{"nums[mid] > nums[right]?"}:::warning

    Check -->|"Да (7 > 2)<br>mid на высоком отрезке"| GoRight["left = mid + 1<br>Минимум строго правее"]:::process
    Check -->|"Нет (1 < 2)<br>mid на низком отрезке"| GoLeft["right = mid<br>Минимум здесь или левее"]:::process

    GoRight --> Loop{"left < right?"}:::warning
    GoLeft --> Loop
    Loop -->|"Да"| Check
    Loop -->|"Нет (left == right)"| End["Возврат nums[left] = 0<br>Точка глобального минимума"]:::success
  

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

package main

// findMin возвращает значение минимального элемента в повернутом
// отсортированном срезе уникальных чисел.
// Временная сложность: O(log N)
// Пространственная сложность: O(1)
func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    // Схлопываем границы до тех пор, пока left != right
    for left < right {
        // Оптимизированное вычисление середины в регистрах ALU
        mid := int(uint(left+right) >> 1)

        if nums[mid] > nums[right] {
            // Высокий отрезок: разрыв находится правее mid
            left = mid + 1
        } else {
            // Низкий отрезок или массив не был повернут вовсе:
            // минимум находится в mid или левее
            right = mid
        }
    }

    // Когда left == right, указатель стоит точно на минимальном элементе
    return nums[left]
}

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

Почему именно nums[right], а не nums[left]?

Попытка сравнения с nums[left] — классическая ошибка новичков. Рассмотрим полностью отсортированный массив, который сдвинули на 0 позиций (то есть не поворачивали вообще): [1, 2, 3, 4, 5].

• Здесь nums[mid] = 3, nums[left] = 1.
• Условие nums[mid] > nums[left] истинно (3 > 1). Если наивно предположить, что минимум справа, алгоритм пойдет вправо и никогда не найдет единицу на нулевом индексе!
• При сравнении же с nums[right] (3 < 5) алгоритм немедленно сжимает right = mid, безошибочно двигаясь к левому краю. Сравнение с right обладает универсальной математической устойчивостью для любых углов поворота.

Поведение Branch Predictor

В процессе бинарного поиска по повернутому массиву интервал поиска очень быстро (за 1–3 шага) целиком локализуется либо строго на правом, либо на исходном отрезке.
Как только оба указателя left и right оказываются внутри единого монотонного сегмента, условие nums[mid] > nums[right] стабильно принимает значение false. Аппаратный предсказатель ветвлений CPU фиксирует данный паттерн и спекулятивно исполняет ветку right = mid, сводя штрафы за сброс конвейера инструкций к абсолютному нулю.

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

Резюме

Поиск точки перелома в повернутом массиве строится на строгом инварианте:

• Сравнение nums[mid] > nums[right] четко разделяет два монотонных сегмента.
• Границы схлопываются в left == right, возвращая точный индекс минимума без лишних проверок.

Теперь мы готовы решить самую знаменитую задачу этого семейства — поиск произвольного значения в повернутом массиве: 7. Search in Rotated Sorted Array.