---
title: "Бинарный поиск во вращённом массиве"
url: https://algopath.pro/ru/patterns/binary-search-rotated
language: ru
summary: "Отсортированный массив, разрезанный и переставленный, на каждом шаге хранит одну отсортированную половину. Найдите её и выберите сторону."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Бинарный поиск (массив)** - Обычный поиск сравнивает середину с целью. Здесь она сначала сравнивается с границей.
- **Линейный поиск** - Перебор справляется с вращённым массивом вообще без рассуждений. Он стоит O(n) вместо O(log n).
- **Бинарный поиск по ответу** - Там отрезок состоит из кандидатов в ответы. Здесь вы ищете реально лежащие значения.
- **Быстрая сортировка (merge / quick)** - Сортировка вернёт порядок, но стоит n log n. Поворот и так оставляет достаточно порядка.

## Бинарный поиск во вращённом массиве: сложность по времени и памяти

n до 1e9 даёт O(log n), как и обычный поиск. Дубликаты доводят худший случай до O(n).

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

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

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

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

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

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

```javascript
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];
}
```

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

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

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

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

## JavaScript

```javascript
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;
}
```

## Python

```python
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
```

## PHP

```php
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;
}
```