# [leetcode] Find Minimum in Rotated Array II

### Find Minimum in Rotated Sorted Array II

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose a sorted array 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.

10/10/2015 udpate

An iterative approach

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

```//How big will the input array be?
//Will the element be negative?
//If duplicated are allowed, the worst case would be o(n)

class Solution {
public:
int findMin(vector<int>& nums) {
return _findMin(nums, 0, nums.size());
}

//[start, end)
int _findMin(vector<int>& nums, int start, int end){
//base condition
if(end - start == 1){
return nums[start];
}
//worst condition
else if(nums[start] == nums[end - 1]){
int mid = (start + end) / 2;
return min(_findMin(nums, start, mid), _findMin(nums, mid, end));
}
//ordinary case
else{
int mid = (start + end) / 2;
if(nums[start] < nums[end - 1]){
//pivot is not in [start, end)
return nums[start];
}
else{
//pivot is in [start, end)
//nums[start] > nums[end - 1]
if(nums[mid] >= nums[start]){
return _findMin(nums, mid + 1, end);
}
else{
return _findMin(nums, start + 1, mid + 1);//BUG: change start to start + 1.
//since numns[start] is bigger than nums[mid], so start can't be the result.
}
}
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.