154.寻找旋转排序数组中的最小值 II

两天宇宙人

2020-02-21

😂二分查找

这个题目有难度，存在相同数字导致它时而取左边界，时而取右边界。

比如[3,3,3,3,1,3,3],这时按理说我查找3，并且取右界，然后与lo + 1的位置比较，取较小的那个即可。

但是如果[3,1,3,3,3,3,3,3],这时如果我查找右界，那么回到倒数第二个3的位置，这就不对了。
同理，单纯取左界也是不对的。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, 
        hi = nums.size() - 1, m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] > nums[hi]) {
                lo = m + 1;
            } else if(nums[m] < nums[hi]){
                hi = m;
            } else {
                hi = hi - 1;
            }
        }
        return nums[lo];
    }
};