寻找旋转排序数组中的最小值
Find Minimum in Rotated Sorted Array
在一个旋转过的升序数组中，找到最小的元素。
在力扣中练习题目描述
已知一个长度为
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.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
解题思路
主解法
二分 · 与右端比较
mid 比右端大就去右半段，否则把右端收到 mid
旋转数组由两段升序组成，最小值是第二段的开头，也是整个数组中唯一“下降”的位置。
比较 nums[mid] 与 nums[right]：
- 如果
nums[mid] > nums[right]，说明 mid 在第一段，最小值一定在 mid 右边，left = mid + 1； - 否则最小值在 mid 或它左边，
right = mid（不能写成 mid-1，因为 mid 自己可能就是答案）。
分步图解
旋转数组分成两段升序；最小值是第二段的开头，也是整个数组唯一“下降”的位置。
自拟数组 [15,18,2,5,9,11]：第一次 mid=2 的值 2 不大于右端 11，right 收到 2；第二次 mid=1 的值 18 大于右端 2，left 移到 2；left 与 right 重合，答案就是 2。
循环用 left < right，结束时 left 就是最小值下标。时间 O(log n)，空间 O(1)。
时间 O(log n)空间 O(1)
易错点
- 与 nums[left] 比较：无法区分“整体有序”和“旋转后最小值在右侧”两种情况。
- else 分支写成 right=mid-1：mid 可能就是最小值，会被跳过。
- 循环条件用 left<=right：最后会在一个元素上继续收缩，越界。
代码与演示
演示输入
nums = [15,18,2,5,9,11]旋转数组分成两段升序；最小值是第二段的开头，也是整个数组唯一“下降”的位置。
查看 C++ 代码
延伸阅读
- 找旋转点、找最小值、找第 k 小都可以用“与右端比较”的二分，关键是保留可能的候选。
- 如果数组允许重复元素，需要先跳过右端与 mid 相等的情况，否则无法判断方向。