题目描述

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

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= 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 ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

算法思路

这道题目麻烦在两个地方，一是数组在某个地方“旋转”了，实际上是一种截断重拍，这会导致本来有序的数组变成了部分有序，也就是两个部分分别有序；另一个就是对于时间复杂度的要求，还是跟上道题目一样，要求$O(logn)$，一想就是二分查找，但是因为问题一导致数组不是有序的，就不能简单的使用朴素二分思路，这里我做了几遍模拟，找到了一个比较蠢但是容易理解的办法，思路如下：

  • 仍然记左右边界为left, right，中间为mid，如果nums[mid] == target，那就直接返回mid即可
  • 如果nums[mid] < target，我们就需要分类讨论了，而不是直接去搜索右区间：
    • 这时候我们考虑一种情况[4, 5, 6, 7, 1]，假设target = 7，此时不难发现：nums[right]=1 < nums[mid]，这说明右半区间必定发生了旋转，最大值出现在右半区间，因此直接搜索右半区见。
    • 否则，nums[right] > nums[mid]，说明右半区见肯定没有旋转，保持递增，这时候我们需要判断nums[right]和target的大小了，因为虽然右半区间在递增，但是target有可能因为“旋转”出现在左半区间，例如nums=[6,7,3,4,5],如果target=4，小于nums[right]，则可以搜索右区；如果target=7，大于nums[right]，那就需要搜索左半区间了。这是一个模拟过程，还是需要动动脑子的。
  • 如果nums[mid] > target，和上面的考虑是一样的，无非是左右互换而已，解题的关键是判断哪一部分有序，也就是根据mid划分之后，哪一部分出现了旋转。

最终的代码如下：

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
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                if (nums[right] < nums[mid]) {
                    // 说明在[mid, right]之间发生了旋转，比如4,5,6,7,1，此时必然在右边
                    left = mid + 1;
                    continue;
                }
                else {
                    // 此时[mid, right]单增，需要比较右端点和target的大小
                    if (nums[right] >= target) {
                        // 还在右侧
                        left = mid + 1;
                        continue;
                    }
                    else {
                        // 搜索左边
                        right = mid - 1;
                        continue;
                    }
                }
            }
            if (nums[mid] > target) {
                if (nums[left] > nums[mid]) {
                    // 说明[mid, left]之间发生了旋转，比如10, 0, 4, 5 ,6，此时必然在左边
                    right = mid - 1;
                    continue;
                }
                else {
                    // 此时[left, mid]单增，需要比较左端点和target的大小
                    if (nums[left] <= target) {
                        right = mid - 1;
                        continue;
                    }
                    else{
                        left = mid + 1;
                        continue;
                    }
                } 
            }
        }
        return -1;
    }
};