[LeetCode] 154. Find Minimum in Rotated Sorted Array II

Posted on | In

Problem

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 1:

1
2
Input: [1,3,5]
Output: 1

Example 2:

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

Note:

Explanation

  1. Similar to 153. Find Minimum in Rotated Sorted Array, this time there’s possibility that nums[left] == nums[mid] == nums[right], and we don’t know which side of the array need to be check.

  2. To solve this, we can simply apply the same method as before, but this time, we add one more if condition, if nums[right] == nums[mid], then we move right to the left 1 step. This method doesn’t affect our solution since we just remove one repeated number.

Solution

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

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right -= 1;
            }
        }

        return nums[left];
    }
}