这道题是快手面经中提到的，在此记录：https://www.nowcoder.com/feed/main/detail/b17a674ca2ba4327b3105ffacd1f60b4

题目

33. 搜索旋转排序数组

整数数组 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
2
3
4
5
6
7
8
9
10
11
示例 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
2
3
4
5
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

思路

本题要求用O(log n)的算法解决这个问题，自然没有办法通过暴力遍历来解决了（不然就太简单了）。

看到log就要想到二分法，同时要想到二分法的前提是遍历的序列已经有序，但这道题并非是一个严格有序的数组，它会进行一定的旋转。

仔细观察旋转的方式，当选用下标k的时候，会将k和k以后的元素全部移动到数组开头，之前的元素移动到数组末尾。

可以拿纸笔多试试几次，就能得出来一个结论，不管数组的长度是奇数还是偶数，也不管k选择那一个地方，被旋转的部分（k和k以后）和没有被旋转的部分（k以前）的序列长度肯定相等或有一个更长！

这里假设二分法计算mid的公式是left+(right-left)/2，其中left初始值为0，right初始值是nums.size()-1，二者都是闭区间。因为上文提到的特性（被旋转的部分和没有被旋转的部分长度相等或有一个更长），使用这个公式计算出来的第一个mid值肯定是在某个有序序列之中！

这里举几个具体的例子：

  • 数组长度7（奇数），k=3，即在下标3处旋转，此时k之前还有下标0,1,2三个数字，k和k以后还有3,4,5,6四个数字；k=4时同理，k之前有四个数字，k以后有三个数字。
    • 此时计算mid=0+(6-0)/2=3，不管k选择什么，下标3肯定是在某个有序序列之中的，这个有序序列要么在下标3之前，要么在下标3之后。
  • 数组长度8（偶数），k=4，此时k之前有0,1,2,3四个数字，k和k之后有下标4,5,6,7四个数字，被旋转和没有被旋转的部分一样长；k=5时没有被旋转的部分更长，k=3时被旋转的部分更长。
    • 此时计算mid=0+(7-0)/2=3，不管k选择哪一个，下标3还是肯定在某个有序序列之中！

现在我们能确认这个特性了，也就能用二分法解决这个问题了！思路就是通过判断mid左侧还是右侧有序，来确认left/right边界，让下一轮的mid计算在有序序列中进行。

  • 如果nums[left]小于等于nums[mid]，则说明左侧有序（这里的等于判断是避免mid=left的情况）
  • 其他情况都可以归于右侧有序

在循环体内，每一次都需要判断mid左侧还是右侧有序的，确认有序序列的位置之后，找target的操作就是在有序数组中通过二分法查找的思想了，时间复杂度是O(log(N))。

  • 为什么每一次都需要判断？

因为target可能不在第一次找到的有序序列中，如下示例，第一次计算出来的mid=3，虽然能确认mid的左侧是有序的，但target=1的时候，我们需要找的目标数是在mid的右侧。此时右侧的序列是[7,0,1,2]，这还不是一个有序序列，我们还是需要通过计算mid判断左侧还是右侧有序，来再次确认第二个有序的子序列位置。

1
[3,4,5,6,7,0,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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 旋转后的数组肯定是一部分有序的
        // 这个有序的部分肯定是在mid左侧或者右侧！
        // 题目中的旋转是从k开始（包括k）往后的数字移动到数组的开头
        // 不管k选择哪里都肯定符合上面的这个条件，永远会有一边的数字更多
        // [4,5,6,7,0,1,2] 以mid=3分割
        // [4,5,6,7]       有序
        //       [7,0,1,2] 无序

        int left = 0, right = nums.size() - 1;
        // 如果要使用小于等于，那么left和right应该都是闭区间
        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;
                }
                continue;
            }
            // 左半部分不是有序，说明右半部分是有序的
            else {
                // 值在右侧
                if (nums[right] >= target && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
                continue;
            }
        }
        return -1;
    }
};

image.png