LeetCode 154. 寻找旋转排序数组中的最小值 II（二分查找）
LeetCode 154. 寻找旋转排序数组中的最小值 II（二分查找）
Michael阿明
发布于 2020-07-13 15:27:59
发布于 2020-07-13 15:27:59
1. 题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。 注意数组中可能存在重复的元素。
示例 1： 输入: [1,3,5] 输出: 1
示例 2： 输入: [2,2,2,0,1] 输出: 0
2. 二分查找
- 不能以左端点作为比较
- 用右端点作为比较，遇到 mid = right，right-1
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.size() == 1||nums.front() < nums.back())
return nums.front();
int l = 0, r = nums.size()-1, mid;
while (l <= r)
{
mid = l +((r-l)>>1);
if(nums[r] < nums[mid])
l = mid+1;
else if(nums[r] > nums[mid])
r = mid;
else
r--;
}
return nums[l];
}
};
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录