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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。

例如，原数组：

nums = [0,1,2,4,5,6,7]

在变化后可能得到：

• 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
• 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为：

[a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值互不相同的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。

请你找出并返回数组中的最小元素。

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

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5]，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17]，旋转 4 次得到输入数组。

提示：

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整数互不相同
• nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

二分查找：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;

        while (left < right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right])
            {
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
        }

        return nums[left];
    }
};

核心思想

旋转排序数组本来是一个升序数组，只是被切开后交换了前后两段。

例如：

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

可以看成：

[4,5,6,7] 和 [0,1,2]

最小值就是第二段的第一个元素，也就是旋转点。

如果数组没有实际改变顺序，例如旋转了 n 次：

[11,13,15,17]

最小值就是第一个元素。

这题最关键的观察是：

比较 nums[mid] 和 nums[right]，可以判断最小值在 mid 的右边，还是在 mid 以及它左边。

因为右端点 nums[right] 位于当前搜索区间的最右侧。

如果 nums[mid] > nums[right]，说明 mid 还在左侧较大的那一段，最小值一定在 mid 右边。

如果 nums[mid] < nums[right]，说明从 mid 到 right 这一段是有序的，最小值可能就是 mid，也可能在 mid 左边。

由于题目保证元素互不相同，不会出现 nums[mid] == nums[right] 的模糊情况。

区间定义

代码维护闭区间：

[left, right]

它表示最小值的下标一定在这个区间内。

初始化时：

int left = 0;
int right = nums.size() - 1;

整个数组都可能包含最小值。

循环条件是：

while (left < right)

当 left == right 时，区间只剩一个位置，这个位置就是最小值所在位置。

二分查找逻辑

每次取中点：

int mid = left + (right - left) / 2;

然后比较：

nums[mid] 和 nums[right]

nums[mid] > nums[right]

这种情况说明 mid 位于旋转点左侧的较大有序段。

例如：

[4,5,6,7,0,1,2]
 left    mid     right

此时 nums[mid] = 7，nums[right] = 2。

由于 nums[mid] > nums[right]，说明从 mid 到 right 之间一定跨过了旋转点。

最小值一定在 mid 的右边。

因此：

left = mid + 1;

nums[mid] < nums[right]

这种情况说明 mid 到 right 是一个正常升序段。

例如：

[4,5,6,7,0,1,2]
         left mid right

此时 nums[mid] = 1，nums[right] = 2。

这一段内部没有旋转断点，最小值不可能在 mid 的右边。

它要么就是 mid，要么在 mid 左边。

因此保留 mid：

right = mid;

这里不能写成 right = mid - 1，因为 mid 自己可能就是最小值。

为什么和右端点比较

比较 nums[mid] 和 nums[right] 的好处是，可以稳定判断最小值相对 mid 的方向。

如果 nums[mid] > nums[right]，右端点比中点小，说明最小值一定在右半边。

如果 nums[mid] < nums[right]，右半段已经有序，右半段最小值就是 nums[mid]，所以真正的全局最小值不会在 mid 右边。

这种判断每次都能排除一半区间。

而且因为数组元素互不相同，不需要处理相等时无法判断方向的问题。

为什么不能直接比较 nums[mid] 和 nums[left]

也可以围绕左端点设计二分，但更容易在边界上绕。

例如：

[3,4,5,1,2]

当 nums[mid] >= nums[left] 时，通常说明左半边有序，最小值在右边。

但如果当前区间本身已经有序，比如：

[11,13,15,17]

一直和左端点比较时，需要额外小心处理“完全有序”的情况。

使用右端点比较时，逻辑更统一：

• nums[mid] > nums[right]，最小值在右边
• nums[mid] < nums[right]，最小值在左边或就是 mid

边界情况

如果数组只有一个元素：

nums = [1]

此时 left == right，循环不会执行，直接返回 nums[0]。

如果数组没有实际改变顺序，例如旋转了 n 次：

nums = [11,13,15,17]

每次都有 nums[mid] < nums[right]，右边界不断左移，最终返回第一个元素。

如果最小值在数组中间，例如：

nums = [4,5,6,7,0,1,2]

算法会通过 nums[mid] > nums[right] 保留右半边，最终定位到 0。

如果最小值在最后一个位置，例如：

nums = [2,3,4,5,1]

多次判断后，左边界会移动到最后一个位置，返回 1。

题目保证数组元素互不相同，所以不会出现重复元素导致无法判断方向的情况。

正确性证明

我们证明：算法返回的 nums[left] 是旋转排序数组中的最小元素。

结论 1：最小值始终位于搜索区间 [left, right] 中

初始化时，搜索区间是整个数组，最小值一定在其中。

每次循环根据 nums[mid] 和 nums[right] 的大小关系缩小区间。

如果 nums[mid] > nums[right]，说明 mid 到 right 之间跨过旋转点，最小值一定在 mid 右边。

算法令：

left = mid + 1

不会排除最小值。

如果 nums[mid] < nums[right]，说明 [mid, right] 是有序段，最小值不可能在 mid 右侧，只可能在 mid 或左侧。

算法令：

right = mid

保留了 mid，也不会排除最小值。

因此每次更新后，最小值始终留在搜索区间中。

结论 2：每次循环都会缩小搜索区间

当 left < right 时，有：

left <= mid < right

如果执行 left = mid + 1，新的左边界会右移。

如果执行 right = mid，由于 mid < right，新的右边界会左移。

所以每次循环都会让搜索区间变短。

结论 3：循环结束时剩余位置就是最小值位置

由结论 2 可知，循环最终一定会结束。

循环结束条件是：

left == right

此时搜索区间中只剩一个下标。

由结论 1 可知，最小值始终在搜索区间中。

因此这个唯一位置就是最小值所在位置。

算法返回 nums[left]，结果正确。

得出结论

由结论 1 可知，算法不会排除真正的最小值。

由结论 2 可知，搜索区间会不断缩小直到只剩一个位置。

由结论 3 可知，最后剩下的位置一定是最小值位置。

因此算法正确。

举例理解

以：

nums = [4,5,6,7,0,1,2]

为例。

二分过程如下：

此时：

left = right = 4

所以最小值是：

nums[4] = 0

再看没有实际改变顺序的情况：

nums = [11,13,15,17]

每次中点值都小于右端点值，说明最小值在左边或就是中点。

最终会收缩到下标 0，返回：

11

复杂度分析

每次二分都会把搜索区间缩小到原来的一半左右。

因此时间复杂度是：

O(log n)

算法只使用了 left、right 和 mid 等常数个变量。

所以空间复杂度是：

O(1)