题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
样例
输入:nums = [3,4,5,1,2]
输出:1
输入:nums = [4,5,6,7,0,1,2]
输出:0
输入:nums = [1]
输出:1
算法1
(二分) $O(logn)$
最小的元素 必然满足 nums[i] <= nums.back(),根据这个二分
时间复杂度 O(logn)
C++ 代码
class Solution {
public:
int findMin(vector<int>& nums) {
/*
最小的元素 必然满足 nums[i] <= nums.back(),根据这个二分
*/
int l = 0, r = nums.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if(nums[mid] <= nums.back()) r = mid;
else l = mid + 1;
}
return nums[r];
}
};