154. Find Minimum in Rotated Sorted Array II

Description

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:

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

Example 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?

Idea

It’s a hard version of problem 153 with duplicates. Here we use three values, left, mid and right. If left is greater than mid, then the minimum locates in (left, mid] and thus we let left auto-increase by 1 and assign the value of mid to right. If left ≤ mid and mid > right, certainly minimum locates in (mid, right]. Under the situation that left ≤ mid <= right, if left < right, then the minimum is left for that there’s only one pivot and if left == right, then we can’t determine whether minimum locates in (left, mid] or (mid, right], thus simply let right auto-decrease by 1 and do the processes again.

Solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int length = nums.size();
        if (length < 0) {
            return -1;
        } else if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return min(nums[0], nums[1]);
        }
        
        int left = 0, right = length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[left] > nums[mid]) {
                left++;
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                if (nums[left] < nums[right]) {
                    return nums[left];
                } else {
                    right--;
                }
            }
        }
        return nums[left];
    }
};