Find Minumu in Rotated Sorted Array II

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii

对于一个有序数组，将其元素以某一个元素为轴进行旋转，比如[0,1,2,3,4,5,6,7]可能会变成[4,5,6,7,0,1,2,3]
求这个经过旋转的数组的最小值，这里数组中存在重复值

如果存在重复值，则需要一个一个的比较，此时最坏的情况下，即所有值都相等的情况下，会把时间复杂度从 \(logN\) 拉到 \(O(n)\)
同时对于存在重复值的有序数组，比如 [1,3,3]这种，需要提前把判断 nums[lo] >= nums[hi]，否则会造成相等判断把 lo 拉上去，远离 最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size()-1;
   
        
        while(lo < hi && nums[lo] >= nums[hi])// 这里加nums[lo]>=nums[hi]是因为如果nums[lo]<nums[hi]，那么此时lo - hi之间的数已经是有序的了，因此直接返回nums[lo]就可以
        {
            int mi = (lo + hi)>>1;
            if(nums[mi] < nums[hi])
                hi=mi;
            else if (nums[mi] > nums[hi])
                lo = mi +1;
            else
                lo = lo+1; // 一个一个往上比较
        }
        return nums[lo];
    }
};

Find Minumu in Rotated Sorted Array II

原文：https://www.cnblogs.com/qiulinzhang/p/12527571.html