153. 寻找旋转数组最小值
题目描述
有一个长度为 n、元素互不相同的升序数组。把它旋转 1 到 n 次，得到输入数组 nums。
旋转一次是指把最后一个元素移到最前面：[a[0], a[1], ..., a[n-1]] 变为 [a[n-1], a[0], ..., a[n-2]]。例如 [0,1,2,4,5,6,7] 旋转 4 次得到 [4,5,6,7,0,1,2]，旋转 7 次又回到原样。
返回 nums 中最小的元素。算法的时间复杂度必须是 O(log n)。
示例 1
输入：nums = [3,4,5,1,2] 输出：1
解释：原数组是 [1,2,3,4,5]，旋转 3 次后得到它，最小值为 1。
示例 2
输入：nums = [4,5,6,7,0,1,2] 输出：0
解释：原数组是 [0,1,2,4,5,6,7]，旋转 4 次后得到它，最小值为 0。
示例 3
输入：nums = [11,13,15,17] 输出：11
解释：旋转 4 次后数组恢复原样，最小值就是首元素 11。
数据范围
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的数两两不同。nums由某个升序数组旋转 1 到n次得到。
解题思路
与右端比较保留最小值区间。
为什么正确
最小值始终在 [lo,hi]。
复杂度分析
时间 O(log n)，额外空间 O(1)。
易错点
注意边界条件并在回溯或弹出后恢复状态。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findMin(self,a):
l,h=0,len(a)-1
while l<h:
m=(l+h)//2
if a[m]>a[h]:l=m+1
else:h=m
return a[l]class Solution {
public int findMin(int[] nums) {
int l = 0, h = nums.length - 1;
while (l < h) {
int m = (l + h) / 2;
if (nums[m] > nums[h]) l = m + 1;
else h = m;
}
return nums[l];
}
}class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, h = nums.size() - 1;
while (l < h) {
int m = (l + h) / 2;
if (nums[m] > nums[h]) l = m + 1;
else h = m;
}
return nums[l];
}
};func findMin(nums []int) int {
l, h := 0, len(nums)-1
for l < h {
m := (l + h) / 2
if nums[m] > nums[h] {
l = m + 1
} else {
h = m
}
}
return nums[l]
}var findMin = function(nums) {
let l = 0, h = nums.length - 1;
while (l < h) {
const m = Math.floor((l + h) / 2);
if (nums[m] > nums[h]) l = m + 1;
else h = m;
}
return nums[l];
};function findMin(nums: number[]): number {
let l = 0, h = nums.length - 1;
while (l < h) {
const m = Math.floor((l + h) / 2);
if (nums[m] > nums[h]) l = m + 1;
else h = m;
}
return nums[l];
};