LeetCode 154 - Find Minimum in Rotated Sorted Array II

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

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

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution 1:

public int findMin(int[] num) {
    int start = 0, end = num.length - 1;
    int min = num[0];
    while(start < end-1) {
        int mid = (start + end) / 2;
        if(num[start] < num[mid]) {
            min = Math.min(min, num[start]);
            start = mid + 1;
        } else if(num[start] > num[mid]) {
            min = Math.min(min, num[mid]);
            end = mid - 1;
        } else {
            start++;
        }
    }
    min = Math.min(min, Math.min(num[start], num[end]));
    return min;
}

 

Solutoin 2:

这是一个更加简单易懂的版本。

public int findMin(int[] num) {  
    int l = 0, h = num.length-1;  
    while(l < h && num[l] >= num[h]) {  
        int m = (l + h) / 2;  
        if(num[m] > num[h]) { // 4 5 6 7 0 1 2, min位于左侧上升沿与右侧上升沿之间  
            l = m + 1;  
        } else if(num[m] < num[h]) { // 7 0 1 2 4 5 6, min位于上升沿左侧  
            h = m;  
        } else { // num[m] == num[h]
            l++;
        }
    }
    return num[l];  
} 

图解一下数组可能出现的情况：