寻找旋转排序数组中的最小值

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

设 $x = nums [mid]$ 是现在二分取到的数。

我们需要判断 $x$ 和数组最小值的位置关系，谁在左边，谁在右边？

把 $x$ 与最后一个数 $nums [n - 1]$ 比大小：

如果 $x > nums [n - 1]$ ，那么可以推出以下结论：
- $nums$ 一定被分成左右两个递增段；
- 第一段的所有元素均大于第二段的所有元素；
- $x$ 在第一段。
- 最小值在第二段。
- 所以 $x$ 一定在最小值的左边。
如果 $x \leq nums [n - 1]$ ，那么 $x$ 一定在第二段。（或者 $nums$ 就是递增数组，此时只有一段。）
- $x$ 要么是最小值，要么在最小值右边。

所以，只需要比较 $x$ 和 $nums [n - 1]$ 的大小关系，就间接地知道了 $x$ 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。

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

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

细节

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

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

这是因为，如果 $nums [n - 1]$ 是数组最小值，那么 $nums$ 分成两段，第一段 $[0, n - 2]$ ，第二段 $[n - 1, n - 1]$ ，且第一段的所有数都大于 $nums [n - 1]$ 。每次 $x$ 和 $nums [n - 1]$ 比大小，一定是 $x > nums [n - 1]$ 。这意味着每次二分更新的都是 $left$ ，那么循环结束后，答案自然就是 $n - 1$ 了。

注：这里有两个概念「二分范围」和「答案范围」。答案确实可以等于 $n - 1$ ，但对于二分来说，代码中的 if (nums[mid] < nums[n - 1]) 在 $mid = n - 1$ 的时候一定不成立，我们可以直接知道 $n - 1$ 是蓝色（根据视频中的红蓝染色法），所以 $n - 1$ 无需在二分区间中。

答疑

问：能否与 $nums [0]$ 比大小？

答：可以，但要多写一点代码。假设 $nums$ 有两段。如果 $nums [mid] > nums [0]$ ，那么 $mid$ 在第一段，在最小值左边；否则， $mid$ 要么是最小值，要么在最小值右边。这种写法需要在 $(0, n)$ 中二分，如果二分结果等于 $n$ ，说明 $nums$ 其实只有一段，答案是 $nums [0]$ 。

Python 解法1C++ 解法1

python

class Solution:
    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 nums[right]

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def findMin(self, nums: List[int]) -> int:
        check = lambda i: nums[i] < nums[-1]
        i = bisect_left(range(len(nums) - 1), True, key=check)
        return nums[i]

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    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;
            (nums[mid] < nums.back() ? right : left) = mid;
        }
        return nums[right];
    }
};

复杂度分析

时间复杂度： $O (\log n)$ ，其中 $n$ 为 $nums$ 的长度。
空间复杂度： $O (1)$ 。

思考题

改成计算 $nums$ 的最大值呢？

请读者实现该问题，以加深对本题的理解。

分类题单

如何科学刷题？

我的题解精选（已分类）

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

细节 ​

答疑 ​

复杂度分析 ​

思考题 ​

分类题单 ​

细节

答疑

复杂度分析

思考题

分类题单