Бинарный поиск во вращённом массиве

Binary search on a rotated array

O(log n)

Отсортированный массив, разрезанный и переставленный, на каждом шаге хранит одну отсортированную половину. Найдите её и выберите сторону.

Elman HuseynovОбновлено 17 окт. 2026 г.

Бинарный поиск во вращённом массиве: как это работает?

Вращённый массив это один отсортированный кусок, разрезанный и переставленный. Каждая из двух частей внутри отсортирована.

Возьмите средний индекс как обычно. Сравните значение там со значением на нижней границе.

Если нижнее значение не больше, отсортирована левая половина. Иначе отсортирована правая.

Теперь одна половина полностью понятна. Её концы ограничивают все значения внутри.

Проверьте, попадает ли цель между этими концами. Если да, ищите в этой половине, иначе в другой.

В любом случае половина отрезка исчезает. Стоимость остаётся log n.

Источники: Википедия: Двоичный поиск

lo=0 hi=6, mid=3, значение 7Ищем 0 в массиве [4, 5, 6, 7, 0, 1, 2].
левая половина от 4 до 7 отсортированаНижнее значение 4, среднее 7. Значит слева переноса нет.
lo=4 hi=60 не попадает между 4 и 7. Ответ должен быть справа.
mid=5, значение 1, левая половина от 0 до 1Левая половина снова отсортирована. На этот раз 0 попадает внутрь.
lo=4 hi=4, значение 0Остался один кандидат, и он подходит. Три шага на семь элементов.

Бинарный поиск во вращённом отсортированном массиве

searchRotated([7, 8, 9, 1, 2, 3, 4, 5, 6], 9)

lo
hi

target = 9lo = 0hi = 8mid = none

Ищем 9 в отсортированном массиве, который разрезали и переставили. Каждая из двух частей внутри отсортирована.

1 / 7

Гонка скорости

Линейный просмотр и бинарный поиск по повёрнутому массиву на одних и тех же 40 числах

Столбики: отсортированные числа, сдвинутые на 14, поэтому наименьшее стоит на позиции 14. Обе дорожки ищут число ближе к концу.

Одна операция: одно чтение элемента. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Линейный просмотр O(n)

операций: 0

Бинарный поиск по повёрнутому массиву O(log n)

операций: 0

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 1 000

Линейный просмотр900 · меньше 1 мс

Бинарный поиск по повёрнутому массиву24,9 · меньше 1 мс

n = 100 000

Линейный просмотр90 тыс. · меньше 1 мс

Бинарный поиск по повёрнутому массиву41,5 · меньше 1 мс

n = 10 000 000

Линейный просмотр9 млн · 90 мс

Бинарный поиск по повёрнутому массиву58,1 · меньше 1 мс

Бинарный поиск во вращённом массиве: шаблон кода

function searchRotated(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[lo] <= arr[mid]) {
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

function searchRotated(arr: number[], target: number): number {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[lo] <= arr[mid]) {
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

def search_rotated(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

function searchRotated(array $arr, $target) {
    $lo = 0; $hi = count($arr) - 1;
    while ($lo <= $hi) {
        $mid = intdiv($lo + $hi, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$lo] <= $arr[$mid]) {
            if ($arr[$lo] <= $target && $target < $arr[$mid]) $hi = $mid - 1;
            else $lo = $mid + 1;
        } else {
            if ($arr[$mid] < $target && $target <= $arr[$hi]) $lo = $mid + 1;
            else $hi = $mid - 1;
        }
    }
    return -1;
}

    public static int searchRotated(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] == target) return mid;
            if (arr[lo] <= arr[mid]) {
                if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    public static int SearchRotated(int[] arr, int target) {
        int lo = 0, hi = arr.Length - 1;
        while (lo <= hi) {
            int mid = (int)(((uint)(lo + hi)) >> 1);
            if (arr[mid] == target) return mid;
            if (arr[lo] <= arr[mid]) {
                if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

Бинарный поиск во вращённом массиве: разбор примера

Минимум во вращённом массиве

Отсортированный массив повернули неизвестное число раз. Найдите его наименьшее значение.

Значения различны, и перебирать весь массив нельзя.

Сравните среднее значение со значением на верхней границе.

Если среднее больше, точка поворота лежит правее. Иначе минимум это середина или что-то левее.

function findMin(nums) {
    let lo = 0;
    let hi = nums.length - 1;

    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);

        // compare against the right end, never the left
        if (nums[mid] > nums[hi]) {
            lo = mid + 1; // the rotation point is further right
        } else {
            hi = mid;     // mid may itself be the minimum
        }
    }

    return nums[lo];
}

Бинарный поиск во вращённом массиве: когда применять?

Паттерн «Бинарный поиск во вращённом массиве» нужен, когда в условии есть слова «отсортированный массив провёрнут в неизвестной точке», «найти цель за O(log n)» или «без дубликатов (или обработать их отдельно)». Решение на нём обычно укладывается в O(log n).

отсортированный массив провёрнут в неизвестной точке
найти цель за O(log n)
без дубликатов (или обработать их отдельно)
найти минимум / точку вращения
массив растёт, а потом один раз падает

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Бинарный поиск во вращённом массиве: с чем путают?

Паттерн «Бинарный поиск во вращённом массиве» чаще всего путают с этими паттернами: Бинарный поиск (массив), Линейный поиск, Бинарный поиск по ответу и Быстрая сортировка (merge / quick).

Бинарный поиск (массив) (Binary search (array)): Обычный поиск сравнивает середину с целью. Здесь она сначала сравнивается с границей.
Линейный поиск (Linear search): Перебор справляется с вращённым массивом вообще без рассуждений. Он стоит O(n) вместо O(log n).
Бинарный поиск по ответу (Binary search on the answer): Там отрезок состоит из кандидатов в ответы. Здесь вы ищете реально лежащие значения.
Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Сортировка вернёт порядок, но стоит n log n. Поворот и так оставляет достаточно порядка.

Бинарный поиск во вращённом массиве: частые ошибки

Сначала сравнивают середину с целью
Цель ничего не говорит о том, какая половина отсортирована. Сравнивайте середину с границей.
Двигают верх за середину при поиске минимума
Средний элемент сам может быть минимумом. Перепрыгнуть его вправе только нижняя граница.
Считают, что поворот точно был
Поворот на ноль это тоже допустимый вход. Проверка отсортированной половины обязана его покрывать.
Не учитывают повторяющиеся значения
Когда на обеих границах одно значение, половину не опознать. Безопасно только сузить отрезок на единицу.

Паттерн «Бинарный поиск во вращённом массиве» решает такие задачи с собеседований: Поиск во вращённом массиве, Поиск во вращённом массиве II, Минимум во вращённом массиве, Минимум во вращённом массиве II, На сколько повернули массив, Индекс пика в горном массиве и Поиск в горном массиве.

Поиск во вращённом массиве: Чистая форма, значения различны.
Поиск во вращённом массиве II: Дубликаты дают линейный худший случай.
Минимум во вращённом массиве: Сравнение идёт с верхней границей, а не с целью.
Минимум во вращённом массиве II: То же самое, но случай дубликатов разбирается вручную.
На сколько повернули массив: Индекс минимума и есть число поворотов.
Индекс пика в горном массиве: То же деление пополам, но по сравнению с соседом.
Поиск в горном массиве: Сначала найдите пик, потом ищите на каждой стороне.