算法：153.寻找旋转排序数组中的最小值
题目
链接：leetcode链接
思路分析（二分）
题目要求O(logN)的时间复杂度，那就必然是使用二分算法了。
怎么个二分呢？
首先，我们来寻找二段性
我们看示例一：
3，4，5，1，2
旋转后，我们可以发现最小元素的左边全部都比最右边的值大，最小元素右边全部都小于等于最右边的值。
根据这一规则，二分不就来了嘛
很明显，是寻找左边界的二分。
细节：
while(left < right) //这里不能取等，不然死循环
mid = left + (right - left) / 2;
left = mid + 1;
right = mid;
题目要求返回最小元素，不是最小元素的下标
代码
int findMin(vector<int>& nums) {
int left = 0,right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] > nums[nums.size() - 1]) left = mid + 1;
else right = mid;
}
return nums[left];
}
原文地址：https://blog.csdn.net/2303_78940834/article/details/142664109
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！