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

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

1 二分查找(注意右边界控制)

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

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

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

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

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|二分查找|153. 寻找旋转排序数组中的最小值

上一篇:超级人脉APP源码


下一篇:未来集市系统开发定制 源码搭建出