33. Поиск в сдвинутом отсортированном массиве (Search in Rotated Sorted Array)

Задание.

Есть целочисленный массив nums, отсортированный в порядке возрастания (с различными значениями).

Nums передаётся в вашу функцию, возможно, повёрнутым с неизвестным индексом поворота k (1 <= k < nums.length) так, чтобы результирующий массив был [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-индексированный).

Например, [0,1,2,4,5,6,7] может быть повернуто в индексом поворота 3 и стать [4,5,6,7,0,1,2].

Итак, дан массив nums после возможного поворота и целочисленный target

Нужно вернить индекс target, если он находится в nums, или -1, если он не находится в nums.

Нужно написать алгоритм со сложностью времени выполнения O(log n).

Пример 1.

Входные данные: nums = [4,5,6,7,0,1,2], target = 0

Результат: 4

Пример 2.

Входные данные: nums = [4,5,6,7,0,1,2], target = 3

Результат: -1

Пример 3.

Входные данные: nums = [1], target = 0

Результат: -1

Решение.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        int s=0,e=size-1,m;

        while(s <= e) {
            m = s + (e-s)/2;
            if(nums[m] == target) return m;
            if( nums[s] <= nums[m] ) { // непрерывная последовательность слева?
                // да
                if(nums[s] == target) {
                    return s;
                } else if(nums[s] < target && target < nums[m]) { // target в левой половине?
                    e = m - 1; // да, отсекаем правую половину
                } else {
                    s = m + 1; // нет, отсекаем левую половину
                }
            } else {
                // непрерывная последовательность справа
                if(nums[e] == target) {
                    return e;
                } else if(nums[m] < target &&  target < nums[e]) { // target в правой половине?
                    s = m + 1; // да, отсекаем левую половину
                } else {
                    e = m - 1; // нет, отсекаем правую половину
                }
            }
        }
        return -1;
    }
};

Алгоритм

Для определения используется дихотомический поиск.

1. Определяется середина последовательности.

2. Определяется, какая из половин последовательности (левая или правая) является непрерывной (если начальное значение последовательности меньше серединной, то непрерывная последовательность слева)

3. Определяется, в какой половине находится target.

4. Для непрерывной последовательности слева, target будет в левой части, если значение target находится между начальным значением и серединой.

5. Для непрерывной последовательности справа, target будет в правой части, если значение target находится между серединой и конечным значением.

6. Если target находится в левой части, нужно отсечь правую и наоборот.