--- title: "Бинарный поиск в повёрнутом массиве: одна половина всегда отсортирована" url: https://algopath.pro/ru/blog/binarnyy-poisk-v-povyornutom-massive language: ru summary: "Как за O(log n) искать в массиве, который сдвинули по кругу. Идея, код на Python для поиска цели и минимума, разбор на примере, случай с дубликатами и типичные ошибки." updated: 2026-10-24 --- # Бинарный поиск в повёрнутом массиве: одна половина всегда отсортирована **Короткий ответ.** Бинарный поиск в повёрнутом массиве работает. Причина: одна из двух половин всегда отсортирована. На каждом шаге находим упорядоченную половину. Потом проверяем, лежит ли цель в ней. Время 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) и объясните: каждый шаг отбрасывает половину. Упомяните дубликаты как отдельный случай, даже если не спросили. Отработать узнавание приёма можно на странице [бинарный поиск во вращённом массиве](/ru/patterns/binary-search-rotated). Основа лежит на странице [бинарный поиск](/ru/patterns/binary-search-array). ## Вопросы и ответы ### Можно ли сначала найти точку поворота, а потом искать обычным поиском? Да, это два бинарных поиска вместо одного. Работает, тоже O(log n). Один проход короче, но двухшаговый вариант проще объяснить. ### Как найти, на сколько позиций повернули массив? Это индекс минимума. Функция find_min выше возвращает значение, верните вместо него lo. В [4, 5, 6, 7, 0, 1, 2] минимум стоит на индексе 4, значит поворот на 4. ### Где приём встречается в реальных системах? В кольцевых буферах логов, где запись идёт по кругу и самая старая строка лежит в середине. Поиск по времени в таком буфере это та же задача. ### Что делать, если массив не повёрнут? Код выше это учитывает. Левая половина всегда будет отсортирована, и поиск сведётся к обычному. ### Как найти пик в массиве, который растёт, потом убывает? Сравните nums[mid] с nums[mid + 1]. Если справа больше, пик справа. Иначе слева или в mid. Та же идея с другим сравнением.