题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 $O(\log n)$ 级别。

样例

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

算法1

(三次二分检索) $O(\log n)$

1. 数组长度为 0 和 1 时的特判处理。
2. 首先二分出是以哪个元素分割数组两部分的。
3. 具体为：每次二分时，如果 nums[mid] >= nums[l] && nums[mid] >= nums[r]，则 l = mid + 1；如果 nums[mid] <= nums[l] && nums[mid] <= nums[r]，则 r = mid；否则 break。最终数组分为 [0, l - 1] 和 [l, n - 1]两段区间。
4. 然后再在两段区间分别二分找 target 即可。

时间复杂度

• 三次二分检索，时间复杂度是 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0)
            return -1;
        if (n == 1)
            return nums[0] == target ? 0 : -1;

        int l = 0, r = n - 1, pivot;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= nums[l] && nums[mid] >= nums[r])
                l = mid + 1;
            else if (nums[mid] <= nums[l] && nums[mid] <= nums[r])
                r = mid;
            else break;
        }
        pivot = l - 1;
        l = 0; r = pivot;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }
        if (nums[l] == target)
            return l;

        l = pivot + 1; r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] < target)
                l = mid + 1;
            else
                r = mid;
        }
        if (nums[l] == target)
            return l;
        return -1;
    }
};

算法2

(一次二分检索) $O(\log n)$

1. 数组长度为 0 则直接返回 -1。
2. 每一次二分，我们具体看一下什么时候答案可能在 [l, mid] 中，什么时候答案可能在 [mid + 1, r]中。
3. 注意到 num[0] 是个非常关键的元素，已知数组被分为 两个升序部分，且后半部分全部比 nums[0] 小，如果 nums[i] >= nums[0]，则说明 [0, i] 一定是升序的，否则 [i, n - 1] 一定是升序的。还可以根据 target 与 nums[0] 的关系，判断出 target 可能属于哪一部分。
4. 根据 3，如果给定了一个位置 mid，我们可以根据 nums[0]、nums[mid] 与 target三者的关系，确定出 target 可能属于哪一段区间。具体看代码注释部分。

时间复杂度

• 只有一次二分检索，时间复杂度为 $O(\log n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0)
            return -1;

        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= nums[0]) { // mid 在数组前半部分。
                if (target > nums[mid])
                    // 可以推出 target 的值一定大于 nums[0]，target 只可能在 [mid + 1, r] 中。
                    l = mid + 1;
                if (target < nums[0])
                    // 可以推出 target 的值一定小于 nums[mid]，target只可能在 [mid + 1, r] 中。
                    l = mid + 1;
                if (target <= nums[mid] && target >= nums[0])
                    // 此时 target 的值处于 nums[0] 和 nums[mid] 中，故可能在 [l, mid] 中。
                    r = mid;
            } else { // mid 在数组后半部分
                if (target >= nums[0])
                    // 可以推出 target 的值一定大于 nums[mid]，target只可能在 [l, mid] 中。
                    r = mid;    
                if (target <= nums[mid])
                    // 可以推出 target 的值一定小于 nums[0]，target只可能在 [l, mid] 中。
                    r = mid;
                if (target > nums[mid] && target < nums[0])
                    // 此时 target 的值处于 nums[0] 和 nums[mid] 中，故可能在 [mid + 1, r] 中。
                    l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
};