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

O(log n)

Бинарный поиск по массиву, который был отсортирован, а потом провёрнут в неизвестной точке: на каждом шаге хотя бы одна половина остаётся правильно отсортированной, нужно определить какая и действовать от этого.

Сигналы

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

Шаблон

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

Похоже, но не то

Бинарный поиск (массив): Обычный бинарный поиск считает, что arr[lo] <= arr[mid] <= arr[hi] всегда выполняется. Вращённый массив отсортирован не полностью, поэтому обычное правило сравнения со средним элементом ломается: сначала нужно определить, какая половина отсортирована, и только потом проверять, лежит ли цель в ней.

отсортированный-но-провёрнутый массив, n до 1e5+, нужна скорость лучше O(n) -> O(log n) время, O(1) память. Вращение плюс требование log n - сигнал, что нужна проверка отсортированной половины, а не обычный бинарный поиск.

Изучить этот паттерн