Двоичный поиск в повёрнутых и неотсортированных массивах
Решайте задачи search-in-rotated-sorted-array и find-minimum-in-rotated-array, определяя на каждом шаге, какая половина отсортирована
«Двоичный поиск в повёрнутых и неотсортированных массивах» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое циклически сдвинутый отсортированный массив
Циклически сдвинутый отсортированный массив — это отсортированный массив, который разрезали в некоторой точке, а затем поменяли две части местами. Например, [4, 5, 6, 7, 0, 1, 2] — это отсортированный массив [0,1,2,4,5,6,7], циклически сдвинутый по индексу 4. Стандартный двоичный поиск здесь не работает, поскольку массив больше не отсортирован целиком.
Основная идея заключается в том, что после любого циклического сдвига хотя бы одна половина массива всегда остаётся отсортированной. Двоичный поиск должен определить, какая именно половина отсортирована, прежде чем решать, куда переместить границы.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingОпределение отсортированной половины
После вычисления mid сравните arr[lo] с arr[mid]. Если arr[lo] <= arr[mid], левая половина отсортирована; в противном случае отсортирована правая половина. Определив, какая половина отсортирована, можно проверить, попадает ли целевое значение в этот отсортированный диапазон, и соответствующим образом сузить область поиска.
Это дерево решений позволяет отбрасывать ровно половину массива на каждом шаге, сохраняя сложность O(log n) даже для циклически сдвинутого массива.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1Пошаговый разбор примера
Рассмотрим пошагово выполнение search_rotated([4,5,6,7,0,1,2], 0). Изначально lo=0, hi=6, mid=3, arr[mid]=7. Находится ли целевое значение 0 в отсортированной левой половине [4..7]? Нет, поэтому устанавливаем lo=4. Теперь lo=4, hi=6, mid=5, arr[mid]=1. Левая половина [0,1] отсортирована (arr[lo]=0 <= arr[mid]=1). Находится ли 0 в диапазоне [0..1)? Да, поэтому устанавливаем hi=4. Теперь lo=4, hi=4, mid=4, arr[4]=0 — значение найдено по индексу 4.
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
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
for s in steps:
print(s)Обработка дубликатов при циклическом сдвиге
Если циклически сдвинутый массив может содержать дубликаты (например, [1,3,1,1,1]), условие nums[lo] == nums[mid] неоднозначно — невозможно определить, какая половина отсортирована. Безопасное решение — увеличить lo (или уменьшить hi) на единицу и повторить проверку. В худшем случае это увеличивает время выполнения до O(n); об этом следует упомянуть интервьюеру.
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif 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 False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # TrueПоиск минимума в циклически сдвинутом отсортированном массиве
В родственной задаче требуется найти минимальный элемент в циклически сдвинутом отсортированном массиве, не выполняя поиск конкретного целевого значения. Минимум всегда находится в неотсортированной половине. На каждом шаге: если arr[mid] > arr[hi], минимум находится в правой половине (lo = mid + 1); в противном случае он находится в левой половине, включая mid (hi = mid). Когда lo == hi, минимум найден.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)Почему arr[lo] <= arr[mid] определяет отсортированную левую половину
Условие arr[lo] <= arr[mid] работает потому, что в отсортированном сегменте (или в сегменте без циклического сдвига) первый элемент всегда является наименьшим. Если arr[lo] <= arr[mid], внутри диапазона [lo..mid] не происходило циклического сдвига, поэтому эта половина отсортирована. Равенство учитывает случай, когда lo == mid: сегмент из одного элемента по определению отсортирован.
И наоборот, если arr[lo] > arr[mid], точка поворота должна находиться между lo и mid, а значит, правая половина [mid..hi] является непрерывным отсортированным сегментом.
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')Анализ сложности
Поиск в циклически сдвинутом отсортированном массиве с помощью двоичного поиска по-прежнему выполняется за O(log n) времени и использует O(1) дополнительной памяти, поскольку на каждой итерации область поиска по-прежнему уменьшается вдвое. Единственное отличие от классического двоичного поиска — дополнительная проверка за постоянное время, позволяющая определить, какая половина отсортирована.
При наличии дубликатов сложность в худшем случае возрастает до O(n), поскольку на каждом шаге может понадобиться увеличивать lo только на единицу. Явно упомяните этот компромисс — это показывает, что вы учитываете граничные случаи, выходящие за рамки обычного сценария.
Пошаговый разбор LeetCode 33
LeetCode 33 «Поиск в циклически сдвинутом отсортированном массиве» — классическая формулировка этой задачи. Ограничения гарантируют отсутствие дубликатов и ровно один циклический сдвиг. Решением служит функция search_rotated, написанная ранее. Ключевые моменты для собеседования: всегда указывайте предположение об отсутствии дубликатов, проверяйте неравенства на конкретном примере с граничным значением и убеждайтесь, что возвращаемый индекс корректен как для найденного, так и для отсутствующего значения.
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: поиск минимума без дубликатов
В задаче LeetCode 153 «Поиск минимума в циклически сдвинутом отсортированном массиве» требуется найти минимум в массиве без дубликатов. Нужно сравнивать arr[mid] с arr[hi], а не с arr[lo], чтобы определить, с какой стороны находится минимум. Если arr[mid] > arr[hi], минимум находится справа; в противном случае он находится в mid или слева от него. Такой поиск сходится к минимуму за O(log n).
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11Число циклических сдвигов и индекс точки поворота
Если вы умеете находить минимальный элемент, то знаете и число циклических сдвигов: индекс минимума в точности равен числу позиций, на которые массив был сдвинут вправо. Например, в [4,5,6,7,0,1,2] минимум находится по индексу 4, поэтому массив был сдвинут на 4 позиции.
Зная точку поворота, можно применить стандартный двоичный поиск, рассматривая индексы по модулю n: real_idx = (mid + pivot) % n. Такая альтернативная формулировка может упростить рассуждения при работе со структурами с циклической индексацией.
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4Объединение всех частей
Если на собеседовании вам встретилась задача о циклически сдвинутом массиве, следуйте этому дереву решений. Сначала определите, требуется ли найти целевое значение или найти минимум. Для поиска целевого значения используйте подход с определением отсортированной половины. Для поиска минимума сравнивайте mid с hi. Если возможны дубликаты, упомяните худший случай O(n) и добавьте резервный вариант с уменьшением границ.
Потренируйтесь, прослеживая выполнение своего кода на трёх классических примерах: без циклического сдвига, со сдвигом на одну позицию и со сдвигом, при котором минимум оказывается на последней позиции.
Быстрая проверка
Проверьте, насколько хорошо вы усвоили понятия из урока «Структуры данных и алгоритмы — подготовка к техническому собеседованию».
Итоги урока
В этом уроке вы узнали: в циклически сдвинутом отсортированном массиве всегда есть хотя бы одна отсортированная половина, перед выбором области поиска нужно сравнить arr[lo] с arr[mid], чтобы определить, какая половина отсортирована, а для поиска минимума используются arr[mid] и arr[hi], чтобы найти точку циклического сдвига. Далее мы рассмотрим варианты двоичного поиска по нижней и верхней границе.
Часто задаваемые вопросы
Урок «Двоичный поиск в повёрнутых и неотсортированных массивах» бесплатный?
Да — полный текст урока «Двоичный поиск в повёрнутых и неотсортированных массивах» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Двоичный поиск в повёрнутых и неотсортированных массивах»?
Решайте задачи search-in-rotated-sorted-array и find-minimum-in-rotated-array, определяя на каждом шаге, какая половина отсортирована Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Двоичный поиск в повёрнутых и неотсортированных массивах»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск: левый, правый, средний
- Двоичный поиск в повёрнутых и неотсортированных массивах
- Нижняя и верхняя границы
- Двоичный поиск по пространству ответов