日野弥生：勉強しよう
LeetCode 153 - 寻找旋转排序数组中的最小值
发表于2025年01月07日
通过观察发现，如果旋转到和原数组一样时，以及数组长度为1时，都满足数组头小于等于数组尾的情况，在进入二分查找之前先行判断。
二分查找时需要注意：
- 二分的条件是判断居中数字是否满足大于数组头或者小于数组尾（该数组被规定为数字不存在相等），这里利用是否大于数组头；
- 循环条件是start比end小一个索引距离，即相邻时。因为查找到仅剩下两个数字时，无需继续执行循环体；
- 二分查找的边界缩小范围是让左边界或者右边界等于居中值，因为居中值也需要进入下一次循环体。（注意此处和一般二分查找的不同）
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums[0]<=nums[nums.size()-1])
return nums[0];
int start=0,end=nums.size()-1,mid=0;
while(start<end-1)
{
mid=(start+end)/2;
if(nums[start]<nums[mid])
start=mid;
else
end=mid;
}
return nums[end];
}
};