搜索旋转排序数组

发表于 | 分类于 | 阅读次数：
本文字数： 1.6k | 阅读时长 ≈ 4 分钟

问题提出

#33 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

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

可以假设数组中不存在重复的元素。算法时间复杂度必须是 O(log n) 级别。

示例:

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

解题思路

要求算法时间复杂度必须是 O(log n) 级别，显然要使用二分法。对一个正常的有序数组采用二分法搜索目标值很简单，而本题有序数组在某个未知点旋转过，假设目标值比中心值大，我们不能保证一定要在右边搜索，因为旋转点可能在中心值的左边，导致左边也有比目标值大的数。

一个比较自然的思路是：找一个中心值不行，那么找两个呢？一开始我考虑在1/3和2/3处取中心点，这两个点（设为x和y）和目标值的大小排序共有6种情况。经分析，只有x<target<y或y<target<x的时候才能缩小范围至1/3，其他情况只能缩小至2/3，这也勉强是一种 O(log n) 的解决方案，但比较复杂，如何简化？

上述思路的复杂性在于这两个中心点将待搜索的区域分为了三个子区间，每次比较不得不考虑三种情况。倘若x在区域的开始的地方，或者y在区域结束的地方，三个区间便减少为两个区间，问题复杂度大大降低。

于是将x设置为中点，y设置为结束的位置，如此一来，x和y的大小比较就可以确定左半边是有序的，还是右半边是有序的，现在仅需考虑四种情况，每次都可以保证搜索区域减小至1/2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int search(vector<int>& nums, int target) {
    int start = 0, end = nums.size() - 1;
    while (start <= end) {
        int middle = (start + end) / 2;
        if (target == nums[middle]) return middle;
        if (target == nums[end]) return end;
        if (nums[middle] < nums[end]) {
            if (target > nums[middle] && target < nums[end]) {
                start = middle + 1; end--;
            } else {
                end = middle - 1;
            }
        } else {
            if (target < nums[middle] && target > nums[end]) {
                end = middle - 1;
            } else {
                start = middle + 1;
                end = end - 1;
            }
        }
    }
    return -1;
}