首页 > 代码库 > LeetCode-Find Minimum in Rotated Sorted Array II-旋转排序数组找最小-二分查找
LeetCode-Find Minimum in Rotated Sorted Array II-旋转排序数组找最小-二分查找
https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
允许重复，也就意味着会有a[l]==a[r]，以及a[mid]==a[r]的情况出现。后者比较好办，从坐标图中看出直接r=mid即可。
前者会有一个问题是当a[mid]==a[r]时，无法确定这个中间值在折线上的位置，此时退化为线性搜索，令l++。所以这个算法最差情况下是O(n)的。
class Solution {public: int n,m; int findMin(vector<int> &num) { vector<int> a=num; n=a.size(); int l=0; int r=n-1; while(l<r){ int mid=(l+r)/2; if(a[l]<a[r]) break; else if (a[l]>a[r]) { if (a[mid]>a[r]) l=mid+1; else r=mid; } else { if(a[mid]>a[r]) l=mid+1; else if (a[mid]<a[r]) r=mid; else l++; } } return a[l]; }};
LeetCode-Find Minimum in Rotated Sorted Array II-旋转排序数组找最小-二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。