154. Find Minimum in Rotated Sorted Array II

做过类似的，那个是没有重复的。
原来做法是：
找最小元素其实就是找最大-》最小过度的那个位置。还是可以用二分，每次二分完有一半肯定是正常的ARRAY，舍弃那一半，检测剩下不正常的，直到剩2个或者1个元素就手动判断。

当时判断正不正常的标准是取中间值，和右边比较，比又变小说明右半边是正常的；否则左半边是正常的，不会出现相等的情况，或者说相等意味着就剩1个元素了，就是要求的。
现在有重复的，就不能通过边界判断了，比如：
3 3 3 3 3 1 2 3
3 1 2 3 3 3 3 3

中间元素和不管左边还是右边都是相等的，没法判断舍弃那边。所以这个时候要缩小范围，R--或者L++，再重新二分，直到不相等位置。

至于题目问的影响，拿第二个：
3 1 2 3 3 3 3 3 来说，假如右边有很多3，每次用中间和右边比较都是相等，然后R--，要R--很多很多次。。
3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
除了第二个是1，其余都是3；甚至整个ARRAY都只有3，那么要R--整个数组，worst case变成了0(n)而不是二分的0(lgN)

public class Solution 
{
    public int findMin(int[] nums) 
    {
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.min(nums[0],nums[1]);
        
        return helper(nums,0,nums.length-1);
    }
    
    
    public int helper(int[] nums, int L ,int R)
    {
        if(R - L == 1) return Math.min(nums[R],nums[L]);
        else if(R == L) return nums[R];
        else
        {
            if(nums[R] == nums[L]) return helper(nums,L+1,R);
            
            int M = L + (R-L)/2;
            
            if(nums[M] > nums[R]) return helper(nums,M+1,R);
            else return helper(nums,L,M);
        }
    }
}

以前看我发朋友圈，说H难度一遍过，佩服地我五体投地。现在看，有的H题略水。。。