154. Find Minimum in Rotated Sorted Array II

Problem:

Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Analysis:
6/19/2018 update:
Since we only compare nums[end], decrease end to remove duplicate.

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

--------------------------------------------------------------------------------------------------------------------------

去除重复，保持二分法区间单调性。
参见http://cqbbshuashua.blogspot.com/2018/01/search-in-rotated-sorted-array-ii.html

Solution:

class Solution {
    public int findMin(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start+ 1< end) {  
            int mid = start+ (end- start)/2;  
            if (nums[mid] > nums[end]){  
                start = mid;  
            }  else if (nums[mid] < nums[end]) {
                end = mid;
            } 
            else if (nums[mid] == nums[start]) start++;
            else {
                end--;
            }
         }
        return nums[start] < nums[end] ? nums[start] : nums[end];        
    }
}