Leetcode-154-Find Minimum in Rot

这题是153题的一个变形，相比153题只多了一个条件，那就是可能包含重复元素。我们先看看若不包含重复元素这题怎么用时间搞定。

其实就是一个简单的BinarySearch，代码如下：

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

加上重复元素这个条件，代码只多了一行，就是的情况。但是就因为这一行，算法的复杂度变成了，而且这个复杂度在worst case情况下不可改进。

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