Бинарный поиск в повёрнутом массиве: одна половина всегда отсортирована

Короткий ответ. Бинарный поиск в повёрнутом массиве работает. Причина: одна из двух половин всегда отсортирована. На каждом шаге находим упорядоченную половину. Потом проверяем, лежит ли цель в ней. Время O(log n). Приём нужен для задач Search in Rotated Sorted Array и Find Minimum. Ниже идея, код на Python, разбор и ошибки.

Что такое повёрнутый массив?

Берём отсортированный массив [1, 2, 3, 4, 5, 6, 7]. Сдвигаем его по кругу на три позиции. Получаем [4, 5, 6, 7, 1, 2, 3]. Это и есть повёрнутый массив.

Он состоит из двух отсортированных кусков. Точка, где большой элемент сменяется маленьким, называется точкой поворота. Здесь это переход от 7 к 1.

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

Как бинарный поиск в повёрнутом массиве выбирает половину?

Берём середину mid. Сравниваем nums[lo] и nums[mid]. Если nums[lo] не больше nums[mid], левая половина отсортирована. Иначе отсортирована правая.

Дальше смотрим на цель. Если цель лежит внутри отсортированной половины по значениям, идём туда. Иначе идём в другую половину.

На каждом шаге диапазон уменьшается вдвое. Отсюда O(log n).

Как это выглядит на примере?

Массив [4, 5, 6, 7, 0, 1, 2], цель 0. lo = 0, hi = 6, mid = 3, nums[mid] = 7. nums[lo] = 4 не больше 7, левая половина отсортирована: от 4 до 7. Цель 0 не в ней, идём вправо: lo = 4.

mid = 5, nums[mid] = 1. nums[lo] = 0 не больше 1, левая половина [0, 1] отсортирована. Цель 0 в ней, hi = 4. mid = 4, nums[mid] = 0. Нашли, ответ 4.

Как написать бинарный поиск в повёрнутом массиве на Python?

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:            # левая половина отсортирована
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # правая половина отсортирована
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:             # минимум справа от mid
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Вторая функция сравнивает mid с правым краем. Если nums[mid] больше nums[hi], точка поворота справа. Иначе она слева или в mid.

Чем задачи на повёрнутый массив отличаются друг от друга?

Задача	С чем сравнивать mid	Дубликаты	Время
Search in Rotated Sorted Array	С nums[lo] и с целью	Нет	O(log n)
Search in Rotated Sorted Array II	То же, плюс сдвиг при равенстве	Да	O(log n), худший O(n)
Find Minimum in Rotated Sorted Array	С nums[hi]	Нет	O(log n)
Найти точку поворота	Индекс минимума	Нет	O(log n)

Что меняется, когда есть дубликаты?

При nums[lo] равном nums[mid] и nums[hi] непонятно, какая половина отсортирована. Например, [1, 1, 1, 0, 1].

Выход: сдвинуть lo на один вправо и hi на один влево. Потом продолжить. В худшем случае это O(n), но на обычных данных остаётся логарифм.

По каким словам в задаче узнать приём?

• «Отсортированный массив повёрнут в неизвестной точке».
• «Найти элемент за O(log n)» в таком массиве.
• «Найти минимум» или «сколько раз повернули».
• «Массив сначала растёт, потом убывает», это соседняя задача про пик.

Как найти минимум в повёрнутом массиве?

Функция find_min выше. Сравниваем середину с правым краем. Если середина больше, минимум справа, и левую половину вместе с серединой отбрасываем. Иначе минимум слева или в середине, правую половину отбрасываем.

Пример [4, 5, 6, 7, 0, 1, 2]. mid = 3, nums[mid] = 7 больше 2, lo = 4. mid = 5, nums[mid] = 1 не больше 2, hi = 5. mid = 4, nums[mid] = 0, hi = 4. Ответ 0.

На каких ошибках ломается решение?

• Сравнивают nums[lo] и nums[mid] через строгое меньше. При lo равном mid половина из одного элемента считается неотсортированной.
• Проверяют цель нестрогими границами с обеих сторон и зацикливаются.
• В find_min сравнивают с nums[lo] вместо nums[hi]. На неповёрнутом массиве это ломается.
• Ищут точку поворота линейно и теряют весь смысл приёма.

Как объяснить приём на собеседовании?

Скажите: одна половина всегда отсортирована. Покажите, как это проверить одним сравнением. Потом скажите, как решить, где цель.

Назовите O(log n) и объясните: каждый шаг отбрасывает половину. Упомяните дубликаты как отдельный случай, даже если не спросили.

Отработать узнавание приёма можно на странице бинарный поиск во вращённом массиве. Основа лежит на странице бинарный поиск.

Вопросы и ответы

Можно ли сначала найти точку поворота, а потом искать обычным поиском?

Да, это два бинарных поиска вместо одного. Работает, тоже O(log n). Один проход короче, но двухшаговый вариант проще объяснить.

Как найти, на сколько позиций повернули массив?

Это индекс минимума. Функция find_min выше возвращает значение, верните вместо него lo. В [4, 5, 6, 7, 0, 1, 2] минимум стоит на индексе 4, значит поворот на 4.

Где приём встречается в реальных системах?

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

Что делать, если массив не повёрнут?

Код выше это учитывает. Левая половина всегда будет отсортирована, и поиск сведётся к обычному.

Как найти пик в массиве, который растёт, потом убывает?

Сравните nums[mid] с nums[mid + 1]. Если справа больше, пик справа. Иначе слева или в mid. Та же идея с другим сравнением.