Циклически сдвинутый отсортированный массив

Сортированный массив после сдвига

Возьмём отсортированный массив [1, 3, 5, 7, 9] и перенесём несколько элементов из начала в конец. Например, получится [5, 7, 9, 1, 3]. Глобальный порядок нарушен, но важное свойство осталось: относительно любой середины хотя бы одна из двух половин отсортирована обычным образом.

Сначала определяем отсортированную половину

static int searchRotated(int[] values, int target) {
    int left = 0;
    int right = values.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (values[mid] == target) {
            return mid;
        }

        if (values[left] <= values[mid]) {
            if (values[left] <= target && target < values[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if (values[mid] < target && target <= values[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1;
}

Если values[left] <= values[mid], левая половина отсортирована. Тогда можно проверить, попадает ли target в её диапазон значений. Если попадает — оставляем левую часть, иначе идём вправо. Для отсортированной правой половины логика симметрична.

Почему сложность остаётся логарифмической

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