1 二分查找(注意右边界控制)
- 情况1——
nums[mid]
在最小值右边或就是最小值
class Solution {
public:
int findMin(vector<int>& nums) {
int size = nums.size();
int left = 0, right = size - 1;
// 不能是left <= right, 当nums={2,1}时,left = mid = 0,按以下二分会得left=mid=right=1,会陷入死循环
while (left < right) {
int mid = left + ((right - left) >> 1);
// 若数组本身就是升序,则直接返回nums[left]
if (nums[mid] < nums[right] && nums[mid] > nums[left])
return nums[left];
// 若mid就是中间最小值,则不能取right = mid - 1,一定要right = mid
if (nums[mid] < nums[right])
right = mid;
else if (nums[mid] > nums[right]) // 但mid大于right则一定不是最小值,因此有left = mid + 1
left = mid + 1;
}
return nums[left];
}
};