# 154. Find Minimum in Rotated Sorted Array II

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

Approach 1: O(n).

Approach 2: binary search -- note that the worse case time complexity could be O(N) for cases like [1,1,1,1,1].

# Code (Python)

Approach 2:

class Solution:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] < nums[right]:
                return nums[left]
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else: # nums[mid] == nums[right]
                right -= 1
        return nums[left]

# Code (C++)

Approach 1:

// O(n).
class Solution {
public:
    int findMin(vector<int>& nums) {
        for (int i = 1; i < nums.size(); ++i)
        {
            if (nums[i] < nums[i-1])
                return nums[i];
        }
        return nums[0];
    }
};

Approach 2:

// O(logn).
class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0;
        int hi = nums.size() - 1;
        while (lo < hi)
        {
            if (nums[lo] < nums[hi])
                return nums[lo];
            else if (nums[lo] == nums[hi])
                hi--; // or lo++;
            else
            {
                int mid = lo + (hi - lo) / 2;
                if (nums[lo] <= nums[mid])
                    lo = mid + 1;
                else
                    hi = mid;
            }
        }
        return nums[lo];
    }
};

// O(logn).
class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0;
        int hi = nums.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[lo] == nums[hi])
                hi--;  // or lo++;
            else if (nums[mid] < nums[lo])
                hi = mid;
            else if (nums[mid] > nums[hi])
                lo = mid + 1;
            else
                break;
        }
        return nums[lo];
    }
};