Leetcode|二分查找|153. 寻找旋转排序数组中的最小值

1 二分查找（注意右边界控制）

• 情况1——nums[mid]在最小值右边或就是最小值

• 情况2——nums[mid]在最小值左边

代码语言：javascript复制

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];
    }
};

leetcode

0 人点赞