Task

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example

Example 1:

1
2

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

Example 2:

1
2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Solution

  • 整体未排好序，不能直接用二分查找
  • 对于峰值，左边和右边的子数组都已排好序。故峰值检测后即可二分查找
  • 该题的峰值检测较容易。由于是将升序数组拆为两个子数组，故使用二分查找即可找到峰值：
    • 边界条件：
      • 若数组长度为1则峰值是该元素
      • 若最左边元素小于最右边元素，则峰值一定是最右边元素。否则左边子数组的所有元素一定大于右边子数组的所有元素
    • 取中点元素：
      • 若中点元素大于其右侧相邻元素，说明中点就是峰值
      • 若中点元素大于最左侧元素，说明中点元素在左侧子数组中，即峰值在右侧子数组
      • 若中点元素小于最左侧元素，说明中点元素在右侧子数组中，即峰值在左侧子数组
  • 时间复杂度：峰值检测和随后的操作都是二分查找，故O(n)
  • 空间复杂度：只用了几个指针，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

// Runtime: 4 ms, faster than 77.31% of C++ online submissions for Search in Rotated Sorted Array.
// Memory Usage: 11.1 MB, less than 24.24% of C++ online submissions for Search in Rotated Sorted Array.
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()==0)
            return -1;
        //检测峰值位置
        int l=0,r=nums.size(),peak=peakDetection(nums);
        //若只有一个子数组则直接返回搜索结果
        if(peak==r-1)
            return binarySearch(nums,l,r,target);
        //两个子数组各自搜索
        int ans_l=binarySearch(nums,l,peak+1,target);
        int ans_r=binarySearch(nums,peak+1,r,target);
        //将搜索结果合并
        return (ans_l!=-1)?ans_l:ans_r;
    }
private:
    //在两段分片递增数组中二分查找峰值
    int peakDetection(const vector<int> &nums){
        int l=0,r=nums.size()-1;
        //边界条件
        if(nums.size()==1)
            return l;
        //若最左边元素小于最右边元素，则峰值必是最右边元素
        if(nums[l]<nums[r])
            return r;
        //二分查找峰值
        while(l<r){
            int m=(l+r)/2;
            //检测到峰值的标志是它比右边相邻值大
            if(nums[m]>nums[m+1])
                return m;
            //未找到峰值则根据中点大小二分
            else if(nums[l]<nums[m])
                l=m+1;
            else
                r=m;
        }
        return l;
    }
    //在局部递增的部分作二分查找
    int binarySearch(const vector<int> &nums,int l,int r,int target){
        while(l<r){
            int m=(l+r)/2;
            if(nums[m]==target)
                return m;
            else if(nums[m]>target)
                r=m;
            else
                l=m+1;
        }
        return -1;
    }
};