Problem 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

Solution:

This question is a follow up for 153. Find Minimum in Rotated Sorted Array. We can still use binary search to solve this question.

  1. two pointers, left and right. In the end, we return the nums[left]
  2. calculate mid to find middle element.
  3. Since the array is sorted, if nums[mid] > nums[right] then we set left to mid+1 because we know the smallest element is on the right side and it’s started position would at least be mid+1.
  4. One thing to notice is that the array contains duplicate elements, if nums[mid] == nums[right] we reduce the right pointer.

For the duplicate elements, it might drag the time complexity to O(n) if it looks like the following array.
"1 1 1 1 1 0 1 1 1 1 1 1 1 1"

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left= 0, right= nums.size()-1;
        int mid= 0;
        while(left< right){
            mid= left+ (right-left)/2;
            if(nums[mid]> nums[right])
                left= mid+1; //set to mid+1 is because nums[mid] is definitely not the smallest element
            else if(nums[mid]< nums[right])
                right= mid;
            else
                //nums[mid]== nums[right]
                right--;
        }
        return nums[left];
    }
};

reference: