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

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

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

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

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

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

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

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

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

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 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)
• •без дубликатов (или обработать их отдельно)
• •найти минимум / точку вращения
• •массив растёт, а потом один раз падает

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

• Бинарный поиск (массив) (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: То же самое, но случай дубликатов разбирается вручную.
• На сколько повернули массив: Индекс минимума и есть число поворотов.
• Индекс пика в горном массиве: То же деление пополам, но по сравнению с соседом.
• Поиск в горном массиве: Сначала найдите пик, потом ищите на каждой стороне.

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

O(log n)

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