题目链接 · 灵神原题解（署名来源）

方法一：两次二分

首先 153. 寻找旋转排序数组中的最小值，找到 $\mathit{\text{nums}}$ 的最小值的下标 $i$。

根据旋转排序数组的定义，下标在 $[0,i-1]$ 中的元素都比下标在 $[i,n-1]$ 中的元素大（注意题目保证 $\mathit{\text{nums}}$ 没有重复元素）。特别地，如果 $i=0$，那么 $\mathit{\text{nums}}$ 是严格递增数组，没有发生旋转。

根据这一性质，分类讨论：

• 如果 $\mathit{\text{target}}>\mathit{\text{nums}}[n-1]$，那么 $\mathit{\text{target}}$ 只可能在子数组 $[0,i-1]$ 中。由于子数组 $[0,i-1]$ 是递增的，我们可以在 $[0,i-1]$ 中二分查找 $\mathit{\text{target}}$。
• 如果 $\mathit{\text{target}}\le \mathit{\text{nums}}[n-1]$，那么 $\mathit{\text{target}}$ 只可能在子数组 $[i,n-1]$ 中。由于子数组 $[i,n-1]$ 是递增的，我们可以在 $[i,n-1]$ 中二分查找 $\mathit{\text{target}}$。

注意上述讨论兼容 $i=0$ 的情况：

• 如果 $\mathit{\text{target}}>\mathit{\text{nums}}[n-1]$，由于 $\mathit{\text{nums}}$ 是递增的，所以 $\mathit{\text{target}}$ 比 $\mathit{\text{nums}}$ 中的每个数都要大，所以 $\mathit{\text{nums}}$ 不存在 $\mathit{\text{target}}$。代码调用 $\mathtt{\text{lowerBound}}$ 传入的 $\mathit{\text{right}}=0$，nums[0] == target 是 $\mathtt{\text{false}}$，最后会返回 $-1$。
• 如果 $\mathit{\text{target}}\le \mathit{\text{nums}}[n-1]$，那么在 $[i,n-1]$ 中二分也就是在 $[0,n-1]$ 中二分。

二分基础知识：【基础算法精讲 04】。

本题视频讲解：【基础算法精讲 05】。

下面代码用的开区间二分，用其他二分写法也是可以的。不同二分写法的区别见 我的题解。

Python 解法1

class Solution:
    # 153. 寻找旋转排序数组中的最小值（返回的是下标）
    def findMin(self, nums: List[int]) -> int:
        left, right = -1, len(nums) - 1  # 开区间 (-1, n-1)
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if nums[mid] < nums[-1]:
                right = mid
            else:
                left = mid
        return right

    # 有序数组中找 target 的下标
    def lower_bound(self, nums: List[int], left: int, right: int, target: int) -> int:
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            # 循环不变量：
            # nums[right] >= target
            # nums[left] < target
            if nums[mid] >= target:
                right = mid  # 范围缩小到 (left, mid)
            else:
                left = mid  # 范围缩小到 (mid, right)
        return right if nums[right] == target else -1

    def search(self, nums: List[int], target: int) -> int:
        i = self.findMin(nums)
        if target > nums[-1]:  # target 只可能在第一段
            return self.lower_bound(nums, -1, i, target)  # 开区间 (-1, i)
        # target 只可能在第二段
        # 由于此时 target <= nums[-1]，所以 lower_bound 中的循环结束后，right < n 一定成立，无需判断 right == n
        return self.lower_bound(nums, i - 1, len(nums), target)  # 开区间 (i-1, n)

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
    // 153. 寻找旋转排序数组中的最小值（返回的是下标）
    int findMin(vector<int>& nums) {
        int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
        while (left + 1 < right) { // 开区间不为空
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums.back()) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    // 有序数组中找 target 的下标
    int lower_bound(vector<int>& nums, int left, int right, int target) {
        while (left + 1 < right) { // 开区间不为空
            // 循环不变量：
            // nums[right] >= target
            // nums[left] < target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return nums[right] == target ? right : -1;
    }

public:
    int search(vector<int>& nums, int target) {
        int i = findMin(nums);
        if (target > nums.back()) { // target 只可能在第一段
            return lower_bound(nums, -1, i, target); // 开区间 (-1, i)
        }
        // target 只可能在第二段
        // 由于此时 target <= nums[n-1]，所以 lower_bound 中的循环结束后，right < n 一定成立，无需判断 right == n
        return lower_bound(nums, i - 1, nums.size(), target); // 开区间 (i-1, n)
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

方法二：一次二分

旋转排序数组有什么性质？

把 $\mathit{\text{nums}}$ 中的某个数 $x$ 与 $\mathit{\text{nums}}[n-1]$ 比大小：

• 如果 $x>\mathit{\text{nums}}[n-1]$，那么可以推出以下结论：
  • $\mathit{\text{nums}}$ 由两个递增段组成。
  • 第一段的所有元素均大于第二段的所有元素。
  • $x$ 在第一段。
• 如果 $x\le \mathit{\text{nums}}[n-1]$，那么 $x$ 在第二段。或者 $\mathit{\text{nums}}$ 就是递增数组，此时只有一段。

写法一

设 $x=\mathit{\text{nums}}[\mathit{\text{mid}}]$ 是我们二分的数。

我们需要判断 $x$ 和 $\mathit{\text{target}}$ 的位置关系，谁在左边，谁在右边？

把 $x$ 和 $\mathit{\text{target}}$ 这两个数都与 $\mathit{\text{nums}}[n-1]$ 比大小，可以知道这两个数分别在哪一段。

分类讨论：

• 如果 $\mathit{\text{target}}>\mathit{\text{nums}}[n-1]\ge x$，那么 $\mathit{\text{target}}$ 在第一段，$x$ 在第二段，说明 $\mathit{\text{target}}$ 在 $x$ 的左边。
• 如果 $x>\mathit{\text{nums}}[n-1]\ge \mathit{\text{target}}$，那么 $x$ 在第一段，$\mathit{\text{target}}$ 在第二段，说明 $\mathit{\text{target}}$ 在 $x$ 的右边。
• 否则 $x$ 和 $\mathit{\text{target}}$ 在同一段。和 $\mathtt{\text{lowerBound}}$ 函数一样，比较 $x$ 和 $\mathit{\text{target}}$ 的大小，即可区分谁在左谁在右。

下面代码用的开区间二分，用其他二分写法也是可以的。

二分的范围可以是 $(-1,n-1)$，也就是闭区间 $[0,n-2]$。

这是因为，如果 $\mathit{\text{target}}=\mathit{\text{nums}}[n-1]$，那么下面代码每次循环更新的都是 $\mathit{\text{left}}$，而 $\mathit{\text{right}}$ 始终不变。循环结束后，答案自然就是 $n-1$ 了。

答疑

问：在 $[0,n-2]$ 中二分，是否需要考虑所有数都比 $\mathit{\text{target}}$ 小的情况？或者更一般地，是否需要考虑 $\mathit{\text{target}}$ 不在 $\mathit{\text{nums}}$ 中的情况？

答：不需要。如果 $\mathit{\text{target}}$ 不在 $\mathit{\text{nums}}$ 中，那么无论最终的 $\mathit{\text{right}}$ 是多少，nums[right] == target 一定不成立，算法一定会返回 $-1$。

Python 解法3

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = -1, len(nums) - 1  # 开区间 (-1, n-1)
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            x = nums[mid]
            if target > nums[-1] >= x:  # target 在第一段，x 在第二段
                right = mid  # 下轮循环去左边找
            elif x > nums[-1] >= target:  # x 在第一段，target 在第二段
                left = mid  # 下轮循环去右边找
            elif x >= target:  # 否则，x 和 target 在同一段，这就和方法一的 lower_bound 一样了
                right = mid
            else:
                left = mid
        return right if nums[right] == target else -1

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int last = nums.back();
        int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
        while (left + 1 < right) { // 开区间不为空
            int mid = left + (right - left) / 2;
            int x = nums[mid];
            if (target > last && x <= last) { // target 在第一段，x 在第二段
                right = mid; // 下轮循环去左边找
            } else if (x > last && target <= last) { // x 在第一段，target 在第二段
                left = mid; // 下轮循环去右边找
            } else if (x >= target) { // 否则，x 和 target 在同一段，这就和方法一的 lower_bound 一样了
                right = mid;
            } else {
                left = mid;
            }
        }
        return nums[right] == target ? right : -1;
    }
};

写法二

下面只讨论 $\mathit{\text{target}}$ 在 $x$ 左边，或者 $x=\mathit{\text{target}}$ 的情况。其余情况 $\mathit{\text{target}}$ 一定在 $x$ 的右边。

• 如果 $x>\mathit{\text{nums}}[n-1]$，说明 $x$ 在第一段中，那么 $\mathit{\text{target}}$ 也必须在第一段中（否则 $\mathit{\text{target}}$ 一定在 $x$ 的右边）且 $x$ 必须大于等于 $\mathit{\text{target}}$。
  • 写成代码就是 target > nums[n - 1] && x >= target。
• 如果 $x\le \mathit{\text{nums}}[n-1]$，说明 $x$ 在第二段中（或者 $\mathit{\text{nums}}$ 只有一段），那么 $\mathit{\text{target}}$ 可以在第一段，也可以在第二段。
  • 如果 $\mathit{\text{target}}$ 在第一段，那么 $\mathit{\text{target}}$ 一定在 $x$ 左边。
  • 如果 $\mathit{\text{target}}$ 在第二段，那么 $x$ 必须大于等于 $\mathit{\text{target}}$。
  • 写成代码就是 target > nums[n - 1] || x >= target。

根据这两种情况，去判断 $x$ 和 $\mathit{\text{target}}$ 的位置关系，从而不断地缩小 $\mathit{\text{target}}$ 所在位置的范围，二分找到 $\mathit{\text{target}}$。

Python 解法5

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def check(i: int) -> bool:
            x = nums[i]
            if x > nums[-1]:
                return target > nums[-1] and x >= target
            return target > nums[-1] or x >= target

        left, right = -1, len(nums) - 1  # 开区间 (-1, n-1)
        while left + 1 < right:  # 开区间不为空
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid
        return right if nums[right] == target else -1

C++ 解法5

// C++ 版待补充

Python 解法6

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def check(i: int) -> bool:
            x = nums[i]
            if x > nums[-1]:
                return target > nums[-1] and x >= target
            return target > nums[-1] or x >= target

        i = bisect_left(range(len(nums) - 1), True, key=check)
        return i if nums[i] == target else -1

C++ 解法6

// C++ 版待补充

C++ 解法7

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int last = nums.back();
        auto check = [&](int i) -> bool {
            int x = nums[i];
            if (x > last) {
                return target > last && x >= target;
            }
            return target > last || x >= target;
        };

        int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)
        while (left + 1 < right) { // 开区间不为空
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid; // 更简洁的写法
        }
        return nums[right] == target ? right : -1;
    }
};

复杂度分析

• 时间复杂度：$\mathcal{O}(\log n)$，其中 $n$ 为 $\mathit{\text{nums}}$ 的长度。
• 空间复杂度：$\mathcal{O}(1)$。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府