# 153. 寻找旋转排序数组中的最小值
# 题目描述
已知一个长度为 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
3
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
2
3
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
2
3
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
# 思路
题目要求O(log n)的时间复杂度，那就应该想到二分查找了。
但这不是简单的二分查找，因为数组被旋转了，不是完全有序的。
# 旋转数组的特点
旋转后的数组，可以分为两段：
- 前半段：较大的元素
- 后半段：较小的元素
比如[4,5,6,7,0,1,2]，前半段是[4,5,6,7]，后半段是[0,1,2]。
最小值就在旋转点，也就是两段的交界处。
# 二分查找怎么做？
关键是判断mid在哪一段。
如果nums[mid] > nums[right]，说明mid在前半段（较大元素），最小值一定在mid右边。
为什么？因为nums[right]在后半段，比前半段的元素都小，而mid比right大，说明mid还在前半段，旋转点（最小值)在mid右边。
如果nums[mid] <= nums[right]，说明mid在后半段（较小元素），最小值在mid左边或就是mid本身。
为什么？因为mid <= right，说明[mid, right]这一段是有序的，旋转点在mid左边。
这样就可以用二分查找不断缩小范围。
注意：为什么用nums[right]而不用nums[left]比较？
因为旋转后，左边可能是大的，也可能是小的，不好判断。但右边一定在某一段里，用right更明确。
# 模拟过程
以 nums = [4, 5, 6, 7, 0, 1, 2] 为例：
二分查找过程：
第1次： left=0, right=6, mid=3, nums[mid]=7 > nums[right]=2
→ mid在前半段，最小值在右边，left = mid + 1 = 4
第2次： left=4, right=6, mid=5, nums[mid]=1 < nums[right]=2
→ mid在后半段，最小值在左边或就是mid，right = mid = 5
第3次： left=4, right=5, mid=4, nums[mid]=0 < nums[right]=1
→ right = mid = 4，left = right，找到最小值 nums[4] = 0
# 解题代码
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]) {
// mid在前半段（较大元素），最小值在右边
left = mid + 1;
} else {
// mid在后半段（较小元素），最小值在左边或就是mid
right = mid;
}
}
return nums[left];
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 复杂度分析
- 时间复杂度：O(log n)，二分查找
- 空间复杂度：O(1)
# 其他语言
# Python3
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
# mid在前半段（较大元素），最小值在右边
left = mid + 1
else:
# mid在后半段（较小元素），最小值在左边或就是mid
right = mid
return nums[left]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Java
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
// mid在前半段（较大元素），最小值在右边
left = mid + 1;
} else {
// mid在后半段（较小元素），最小值在左边或就是mid
right = mid;
}
}
return nums[left];
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Go
func findMin(nums []int) int {
left, right := 0, len(nums) - 1
for left < right {
mid := left + (right - left) / 2
if nums[mid] > nums[right] {
// mid在前半段（较大元素），最小值在右边
left = mid + 1
} else {
// mid在后半段（较小元素），最小值在左边或就是mid
right = mid
}
}
return nums[left]
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# JavaScript
var findMin = function(nums) {
let left = 0;
let right = nums.length - 1;
while (left < right) {
let mid = left + Math.floor((right - left) / 2);
if (nums[mid] > nums[right]) {
// mid在前半段（较大元素），最小值在右边
left = mid + 1;
} else {
// mid在后半段（较小元素），最小值在左边或就是mid
right = mid;
}
}
return nums[left];
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 与代码随想录联系
这道题是二分查找在旋转数组中的应用。
我在代码随想录二分查找章节里，详细讲解了二分查找的模板和变体，建议录友们先看代码随想录二分查找章节。
Hot100 里还有一道相关题目：33.搜索旋转排序数组，那道题是在旋转数组中搜索目标值，思路类似，都是先判断mid在哪一段，再决定往哪边搜索。
本题的关键点：
- 用right而不用left比较，因为right的位置更明确
- 循环条件是left < right，最后left == right时就找到了最小值
- right = mid而不是mid - 1，因为mid本身可能就是最小值
录友们做完这道题后，建议画图模拟一遍，理解为什么这样判断就能找到最小值。
评论
验证登录状态...