搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k 上进行了向左旋转，使数组变为：

[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，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

必须设计一个时间复杂度为 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

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

二分查找：

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

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

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

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

        return -1;
    }
};

核心思想

如果数组没有旋转，就是普通的升序数组，可以直接二分查找。

旋转之后，整个数组不再完全有序，但它仍然由两个有序段组成。

例如：

[4,5,6,7,0,1,2]

可以看成：

[4,5,6,7] 和 [0,1,2]

所以普通二分不能直接根据 nums[mid] < target 就判断答案一定在右边。

但旋转数组还有一个非常重要的性质：

任意取一个中点 mid，区间 [left, mid] 和 [mid, right] 中，至少有一半是有序的。

因此每次二分时，先判断哪一半有序。

如果 target 落在有序的那一半，就保留那一半。

否则，说明 target 只能在另一半。

这样每次仍然可以排除一半区间，所以时间复杂度仍然是 O(log n)。

为什么一定有一半有序

旋转数组本质上是把原来的升序数组切成两段，然后交换前后顺序。

所以数组中最多只有一个位置发生“下降”：

前一个数 > 后一个数

例如：

[4,5,6,7,0,1,2]

下降点在 7 -> 0。

对于当前搜索区间 [left, right]，取中点 mid 后：

• 如果下降点不在 [left, mid] 中，那么左半边 [left, mid] 有序。
• 如果下降点在 [left, mid] 中，那么右半边 [mid, right] 一定有序。

因此左右两半至少有一半可以当作普通有序数组来判断范围。

如何判断哪一半有序

因为数组元素互不相同，所以可以通过端点比较判断。

如果：

nums[left] <= nums[mid]

说明 [left, mid] 是有序的。

这时如果：

nums[left] <= target && target < nums[mid]

说明 target 位于左半边的取值范围内，应该继续搜索左半边：

right = mid - 1;

否则，target 不可能在左半边，只能搜索右半边：

left = mid + 1;

如果：

nums[left] > nums[mid]

说明旋转点在左半边里，那么右半边 [mid, right] 一定有序。

这时如果：

nums[mid] < target && target <= nums[right]

说明 target 位于右半边的取值范围内，继续搜索右半边：

left = mid + 1;

否则，target 不可能在右半边，只能搜索左半边：

right = mid - 1;

为什么比较时一边用严格不等

在进入左右区间判断之前，代码已经检查过：

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

所以后面判断目标是否在左半边时，范围写成：

nums[left] <= target && target < nums[mid]

这里右侧使用 < nums[mid]，因为 nums[mid] 已经确认不是答案。

同理，判断目标是否在右半边时，范围写成：

nums[mid] < target && target <= nums[right]

这里左侧使用 nums[mid] < target，也是因为 mid 本身已经被排除。

为什么不能直接套普通二分

普通二分依赖整个搜索区间有序。

当 nums[mid] < target 时，普通二分会认为左边都更小，可以直接去右边。

但在旋转数组中，这个判断可能是错的。

例如：

nums = [4,5,6,7,0,1,2]
target = 0

如果 mid 指向 7，虽然 7 > 0，但答案并不在左半边，而是在右半边。

原因是旋转点破坏了整体有序性。

所以必须先判断哪一半有序，再根据有序半边的范围排除区间。

边界情况

如果数组只有一个元素，循环会检查这个元素是否等于 target。

如果相等，返回 0；否则返回 -1。

如果数组没有实际旋转，也就是 k = 0，整个数组有序。

此时每次都会判断左半边有序，算法退化成普通二分查找。

如果 target 在旋转点附近，例如 [4,5,6,7,0,1,2] 中的 0，算法会通过有序半边范围判断逐步保留包含旋转点的那一侧。

如果 target 小于所有元素或大于所有元素，最终搜索区间会变为空，返回 -1。

题目保证元素互不相同，所以不会出现因为重复元素导致无法判断哪一半有序的情况。

正确性证明

我们证明：算法能正确返回 target 在旋转排序数组中的下标；如果不存在，则返回 -1。

结论 1：每轮循环至少有一半区间是有序的

旋转排序数组最多只有一个下降点。

对于任意搜索区间 [left, right] 和中点 mid，下降点不可能同时破坏 [left, mid] 和 [mid, right] 两个区间。

因此这两个区间中至少有一个是有序的。

代码通过 nums[left] <= nums[mid] 判断左半边是否有序。

如果左半边无序，那么右半边一定有序。

结论 2：当左半边有序时，算法不会错误排除答案

如果 [left, mid] 有序，并且：

nums[left] <= target && target < nums[mid]

那么 target 只能位于左半边，算法令 right = mid - 1，保留了答案可能存在的区间。

如果这个条件不成立，由于左半边有序，并且 nums[mid] 已经不是答案，那么 target 不可能在 [left, mid] 中。

算法令 left = mid + 1，排除左半边，不会排除真正答案。

结论 3：当右半边有序时，算法不会错误排除答案

如果 [mid, right] 有序，并且：

nums[mid] < target && target <= nums[right]

那么 target 只能位于右半边，算法令 left = mid + 1，保留了答案可能存在的区间。

如果这个条件不成立，由于右半边有序，并且 nums[mid] 已经不是答案，那么 target 不可能在 [mid, right] 中。

算法令 right = mid - 1，排除右半边，不会排除真正答案。

结论 4：如果 target 存在，算法一定会找到它

初始搜索区间是整个数组。

由结论 2 和结论 3 可知，每次缩小区间时，如果 target 存在，它都不会被排除。

同时，每轮都会排除至少一个元素，搜索区间不断缩小。

因此如果 target 存在，最终某一轮一定会出现：

nums[mid] == target

算法会返回对应下标。

结论 5：如果算法返回 -1，说明 target 不存在

算法只有在搜索区间变为空，也就是 left > right 后才返回 -1。

根据结论 2 和结论 3，缩小区间时不会错误排除可能包含 target 的位置。

因此当区间为空时，说明数组中不存在 target。

返回 -1 正确。

得出结论

由结论 1 可知，每轮二分都能找到至少一个有序半边。

由结论 2 和结论 3 可知，算法根据有序半边缩小区间时不会排除真正答案。

由结论 4 可知，target 存在时算法一定会返回它的下标。

由结论 5 可知，target 不存在时算法返回 -1。

因此算法正确。

举例理解

以：

nums = [4,5,6,7,0,1,2], target = 0

为例。

二分过程如下：

最终返回：

4

如果 target = 3，每次二分都会排除不可能包含 3 的有序半边或另一半。

最终搜索区间为空，返回：

-1

复杂度分析

每次循环都会排除大约一半搜索区间。

因此时间复杂度是：

O(log n)

算法只使用了 left、right、mid 等常数个变量。

所以空间复杂度是：

O(1)