寻找旋转排序数组中的最小值
Find Minimum in Rotated Sorted Array
本机进度仅保存在当前浏览器
题目描述
已知一个长度为 n 的数组原本按升序排序，经 1 到 n 次旋转后得到输入数组，请找出其中的最小元素。要求 O(log n)。
示例：nums = [3, 4, 5, 1, 2]，输出 1。
解题思路
- 最小值是「第二段升序」的开头；与右端点 nums[r] 比较是这类题的关键技巧。
- nums[mid] > nums[r]：最小值一定在 mid 右侧，l = mid + 1。
- nums[mid] < nums[r]：mid 到 r 之间是有序的，最小值在 mid 及其左侧，r = mid。
- 循环以 l < r 为条件，结束时 l == r 即最小值下标；与找目标值不同，这里不需要命中判断。
参考实现
查看参考实现Python · 建议先自行作答
def findMin(nums):
# 与右端点比较，收缩包含最小值的区间
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]