Search in Rotated Sorted Array

Q: Какова временная сложность поиска в отсортированном массиве с циклическим сдвигом?

Время O(log n) и дополнительная память O(1) . На каждом шаге остается одна половина диапазона, поэтому для 5000 элементов требуется не более 13 шагов. Сначала найти точку поворота — тоже O(log n) , при этом шагов примерно вдвое больше.

Q: Работает ли алгоритм, если массив содержит дубликаты?

Не в таком виде. Когда nums[lo] , nums[mid] и nums[hi] равны, нельзя доказать, что какая-либо из половин отсортирована. Обычно в таком случае lo сдвигают вперёд на единицу: это сохраняет правильность ответа, но приводит к худшей сложности O(n) .

Q: Сначала найти точку поворота или выполнить поиск за один проход?

Оба работают за O(log n) . Сначала поиск минимума разбивает задачу на два обычных двоичных поиска. Поиск за один проход выполняет задачу в одном цикле и требует меньше шагов — именно эту версию ожидает большинство интервьюеров.

СреднеБинарный поиск

+10

Список различных целых чисел был отсортирован по возрастанию, а затем циклически сдвинут: некоторое количество элементов, возможно ноль, взяли из начала и переместили в конец в том же порядке. Например, после циклического сдвига [2, 5, 8, 11, 15, 19, 23] на 4 позиции получится [15, 19, 23, 2, 5, 8, 11]. Вам даны циклически сдвинутый список nums и целое число target. Верните индекс target в nums, считая с 0, или -1, если его нет в списке, за время O(log n).

Функция

search(nums: integer-array, target: integer) → integer

numsinteger-array: циклически сдвинутый отсортированный список различных целых чисел
targetinteger: значение, которое нужно искать
Возвращаетinteger: индекс target в nums или -1, если он отсутствует

Ограничения

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
Все значения в nums различны.
nums — это список, отсортированный по возрастанию и циклически сдвинутый на некоторое k, где 0 ≤ k < nums.length; k = 0 оставляет его без сдвига.

Примеры

Ввод: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Вывод: 4
Пояснение: Первый средний элемент, индекс 3, содержит 2, поэтому правая половина [2, 5, 8, 11] отсортирована и содержит 5. Следующий средний элемент, индекс 5, содержит 8; отсортированная левая часть [5, 8] содержит 5, что приводит к индексу 4.

Ввод: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Вывод: -1
Пояснение: 65 находилось бы между 60 и 70, и ни один элемент его не содержит. Первый средний элемент, 70, помещает 65 в отсортированную левую часть [40, 50, 60, 70], и диапазон там сужается, пока не станет пустым.

Ввод: nums = [8, 13, 21, 1, 3, 5]target = 13
Вывод: 1
Пояснение: Первый средний элемент, индекс 2, содержит 21. Левая часть [8, 13, 21] отсортирована, и 13 находится между 8 и 21, поэтому правая часть отбрасывается. Затем поиск находит 13 по индексу 1.

Дополнительный вопрос

Если nums может содержать дубликаты, ни один алгоритм не может гарантировать O(log n). Можешь доказать это на повёрнутом списке из единиц, скрывающем единственный 0?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Повернутый отсортированный список состоит из двух отсортированных последовательностей: [15, 19, 23], а затем [2, 5, 8, 11]. Сравнение target со средним значением больше не подсказывает, в какой половине оно находится. Но как бы вы ни разделили список, хотя бы одна половина будет отсортирована, и одного сравнения достаточно, чтобы определить, может ли target находиться в этой половине.

Просканируй каждый элемент

Идея

Проверьте каждый индекс и верните первый, значение которого равно target, или -1 после цикла. Алгоритм считывает каждый элемент, поэтому он корректен для любого списка. Он не учитывает два отсортированных участка: для 5000 элементов потребуется до 5000 сравнений, тогда как бинарному поиску нужно 13.

Алгоритм

Для каждого индекса i от 0 до n-1 сравни nums[i] с target.
Если они равны, верни i.
После цикла верни -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Найди точку поворота, затем выполни двоичный поиск

Идея

Второй отсортированный участок начинается с наименьшего значения; обозначим его индекс как k. И nums[k..n-1], и nums[0..k-1] отсортированы, причём каждое значение в первом участке больше любого значения во втором. Зная k, можно сравнить target с nums[k] и nums[n-1], чтобы выбрать участок, а затем завершить поиск обычным двоичным поиском.

Чтобы найти k, сравните среднее значение с nums[hi]. Если nums[mid] > nums[hi], значения где-то после mid убывают, поэтому минимум находится справа от него. В противном случае значения в nums[mid..hi] возрастают без убывания, поэтому минимум находится на позиции mid или левее. В первом примере средние значения — 2, 19 и 23, откуда k = 3, а 5 находится между nums[3] = 2 и nums[6] = 11. Два двоичных поиска требуют примерно 2 log2 n шагов.

Алгоритм

Установите lo = 0 и hi = n-1. Пока lo < hi, вычисляйте mid; если nums[mid] > nums[hi], установите lo = mid + 1, иначе установите hi = mid.
В конечном индексе k находится наименьшее значение.
Если nums[k] ≤ target ≤ nums[n-1], выполните бинарный поиск по индексам от k до n-1; иначе ищите от 0 до k-1.
Верните найденный индекс или -1, если диапазон опустеет.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Один бинарный поиск в отсортированной половине

Идея

Соблюдай обещание бинарного поиска: если target находится в списке, его индекс лежит между lo и hi. Значения уменьшаются только один раз во всём списке, поэтому не более чем одна из двух половин по обе стороны от mid содержит этот переход, а другая отсортирована. Если nums[lo] ≤ nums[mid], левая половина отсортирована; иначе отсортирована правая.

Для отсортированной половины проверка диапазона по двум её концам показывает, может ли target находиться внутри, например nums[lo] ≤ target < nums[mid] для левой половины. Если может, ищи там; если нет, target может находиться только в другой половине. На каждом шаге диапазон делится пополам: для 5000 элементов понадобится не более 13 шагов.

Алгоритм

Установи lo = 0 и hi = n-1.
Пока lo ≤ hi, вычисляй mid и возвращай его, если nums[mid] равен target.
Если nums[lo] ≤ nums[mid], левая половина отсортирована: установи hi = mid - 1, когда nums[lo] ≤ target < nums[mid], иначе установи lo = mid + 1.
Иначе отсортирована правая половина: установи lo = mid + 1, когда nums[mid] < target ≤ nums[hi], иначе установи hi = mid - 1.
Когда цикл завершится, верни -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Ловушки и крайние случаи

Запись nums[lo] < nums[mid] вместо ≤. Когда остаются два элемента, mid равен lo, и строгая проверка считает [9, 4] отсортированной правой половиной: target = 4 возвращает -1.
Сначала сравнивать target с nums[mid]. В первом примере с target = 19 среднее значение 2 меньше, поэтому поиск перемещается вправо и пропускает индекс 1.
Проверять только один конец отсортированной половины. В [40, 50, 60, 70, 80, 10, 20] при target = 80 условие target ≥ nums[lo] само по себе направляет поиск в [40, 50, 60, 70].
В Rust выражение k - 1 для типа usize приводит к переполнению снизу при k = 0, то есть для невращённого списка. Используй полуоткрытые диапазоны.
В Lua и R возвращать позицию с нумерацией от 1. Вычти 1.

Частые вопросы3

Какова временная сложность поиска в отсортированном массиве с циклическим сдвигом?

Время O(log n) и дополнительная память O(1). На каждом шаге остается одна половина диапазона, поэтому для 5000 элементов требуется не более 13 шагов. Сначала найти точку поворота — тоже O(log n), при этом шагов примерно вдвое больше.

Работает ли алгоритм, если массив содержит дубликаты?

Не в таком виде. Когда nums[lo], nums[mid] и nums[hi] равны, нельзя доказать, что какая-либо из половин отсортирована. Обычно в таком случае lo сдвигают вперёд на единицу: это сохраняет правильность ответа, но приводит к худшей сложности O(n).

Сначала найти точку поворота или выполнить поиск за один проход?

Оба работают за O(log n). Сначала поиск минимума разбивает задачу на два обычных двоичных поиска. Поиск за один проход выполняет задачу в одном цикле и требует меньше шагов — именно эту версию ожидает большинство интервьюеров.

def search(nums, target):
    # Напишите здесь код

Тест #1

Тест #2

Тест #3

Аргументы

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Ожидаемый вывод

Search in Rotated Sorted Array

Функция

Ограничения

Примеры

Подсказки

Решение

Просканируй каждый элемент

Найди точку поворота, затем выполни двоичный поиск

Один бинарный поиск в отсортированной половине

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи