距离上次更新本文已经过去了 370 天，文章部分内容可能已经过时，请注意甄别

这道题是快手面经中提到的，在此记录：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) 的算法解决此问题。

plaintext
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

提示：

plaintext
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 判断左侧还是右侧有序，来再次确认第二个有序的子序列位置。

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

代码

思路理清楚了，代码就不难写了

cpp
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