Поиск в Повёрнутом МассивеRotated Sorted Array Search

В 2.2.3.1 инвариант диапазона [lo, hi] опирался на глобальную монотонность: a[i] < x влечёт a[j] < x для всех j < i. В повёрнутом массиве этой глобальной монотонности нет — но зато на каждом шаге можно определить, какая из двух половин [lo, mid] и [mid, hi] осталась строго отсортированной, сравнив a[lo] и a[mid]. Если a[lo] ≤ a[mid] — левая половина отсортирована обычным образом; иначе — излом внутри левой половины, а значит правая половина отсортирована. Как только известно, какая половина "нормальная", проверка "лежит ли x внутри её диапазона значений" делается за O(1), и по ней принимается решение, куда двигаться — точно так же, как в обычном бинарном поиске, только предикат сдвига стал двухшаговым вместо одношагового.In 2.2.3.1, the [lo, hi] range invariant relied on global monotonicity: a[i] < x implies a[j] < x for all j < i. In a rotated array that global monotonicity is gone — but at every step it's possible to determine which of the two halves [lo, mid] and [mid, hi] remains strictly sorted, by comparing a[lo] and a[mid]. If a[lo] ≤ a[mid], the left half is sorted normally; otherwise the break is inside the left half, meaning the right half is sorted. Once it's known which half is "normal," checking "does x fall inside its value range" is O(1), and that decides which way to move — exactly like plain binary search, except the shift predicate became two-step instead of one-step.

int search_rotated(const std::vector<int>& a, int x) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;

        if (a[lo] <= a[mid]) { // левая половина строго отсортирована// left half is strictly sorted
            if (a[lo] <= x && x < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else { // правая половина строго отсортирована// right half is strictly sorted
            if (a[mid] < x && x <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Столбики — отсортированный массив без повторов, повёрнутый на случайное число позиций (точка излома отмечена вертикальной линией). Зелёная половина — строго отсортированная (по ней принимается решение), синяя рамка — текущий диапазон [lo, hi], жёлтый столбик — mid.The bars are a duplicate-free sorted array rotated by a random number of positions (the break point is marked with a vertical line). The green half is strictly sorted (the one the decision is based on), the blue outline is the current range [lo, hi], the yellow bar is mid.

Можно — и это тоже O(log n) (сначала бинарным поиском найти минимум массива, то есть точку излома, потом обычный бинарный поиск в нужной половине) — но это два прохода вместо одного, с удвоенной константой. Показанный здесь способ решает задачу за один проход, потому что не нужно знать точку излома явно: на каждом шаге достаточно знать, какая из двух половин относительно текущего диапазона отсортирована, а это локальная информация, не требующая отдельного поиска.You can — and that's also O(log n) (first binary-search for the array's minimum, i.e. the break point, then run a plain binary search in the correct half) — but that's two passes instead of one, doubling the constant. The approach shown here solves it in a single pass because the break point doesn't need to be known explicitly: at each step it's enough to know which of the two halves is sorted relative to the current range, and that's local information that doesn't require a separate search.

Условие "ровно один излом" — не техническая деталь, а то, что делает задачу вообще разрешимой за O(log n): при двух и более изломах сравнение a[lo] с a[mid] больше не позволяет однозначно определить, какая половина отсортирована (обе могут содержать излом), и гарантия ломается.The "exactly one break" condition isn't a technicality — it's what makes the problem solvable in O(log n) at all: with two or more breaks, comparing a[lo] to a[mid] no longer reliably determines which half is sorted (both can contain a break), and the guarantee falls apart.