154. Find Minimum in Rotated Sorted Array II

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

2. Example

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

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

3. 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?

4. Solutions

My Accepted Solution

n = i_nums.size()
Time complexity: O($log_2n > n$)
Space complexity: O(1)

duplicates will affect the run-time complexity, that’s because if the pivot value and the border value are equal, we don’t know the min value’s position. so, we can’t exclude half values but only one value. then, if all values are equal, the complexity will degenerate to O(n)

class Solution 
{
public:
    // int findMin(vector<int>& nums)
    int findMin(vector<int> &i_nums) 
    {
        if(i_nums.empty()) return -1;

        int minValue;
        for(int left = 0, right = i_nums.size() - 1; left <= right; )
        {
            int pivot = left + ((right - left) >> 1);

            if(i_nums[pivot] < i_nums[right])
                right = pivot;
            else if(i_nums[pivot] > i_nums[right])
                left = pivot + 1;
            else
                right--;

            minValue = i_nums[pivot];
        }

        return minValue;
    }
};