[LeetCode] Problem 154 - Find Minimum in Rotated Sorted Array II

Posted on | In ,

Suppose an array sorted in ascending order 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.

Example

No.1

Input: [1,3,5]

Output: 1

No.2

Input: [2,2,2,0,1]

Output: 0

Note

This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int middle = (left + right) >> 1;

        if (nums[middle] > nums[right])
            left = middle + 1;
        else if (nums[middle] < nums[left])
            right = middle;
        else
            right--;
    }

    return nums[left];
}