[Leetcode] 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.

The code in this post is somewhat complicated, I have posted another solution on my gist which is available here:https://gist.github.com/pyemma/2dbe6f9bbb43f3881153

The key idea is to use the relationship of A[mid] with A[left] and A[right], here, left and right corresponding the portion of subarray we are trying to find the minimum. If there is no duplicate, we could first compare A[mid] with its left and right neighbor to see if we have find the answer, if no answer, we shrink the array we trying to find the minimum.

If the original array is in increasing order, then we directly return A[0]. However, if not, like the example, we could find that there are two monotony interval, from 4 to 7 and from 0 to 2. The element in the first one would all be larger than or equal to the one in the second one. We could easily get:

1. If A[mid] > A[left], then we must located in the first interval, and what we need to do is to discard the portion of array before mid, since the minimum would not be there.
2. If A[mid] < A[right], then we must located in the second interval, we could discard all the array behind the mid.
3. If we could not make a judgement, since there are duplicates. So we move left and right until we could make a judge. Since these duplicates are of no use, discarding them would be okay.

public class Solution {
    public int findMin(int[] num) {
        int n = num.length;
        if(n == 1 || num[0] < num[n-1])
            return num[0];
        int l = 0, r = n-1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(mid > 0 && num[mid] < num[mid-1])
                return num[mid];
            if(mid < n-1 && num[mid] > num[mid+1])
                return num[mid+1];
            if(num[mid] > num[l])
                l = mid + 1;
            else if(num[mid] < num[r])
                r = mid - 1;
            else {
                while(l < mid && num[mid] == num[l])
                    l++;
                while(r > mid && num[mid] == num[r])
                    r--;
            }
        }
        return num[l];
    }
}