# 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];
}
};