## Find Minimum in Rotated Sorted Array II

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.

Analysis:
The solution is similar to the previous question (here), only difference is we can 'skip' the duplicates before determining if the sub array is ordered.

### Code(C++):

class Solution {
public:
void bs(vector<int> &num, int st,int ed, int &res){
if (st>ed){ return; }
else {
int mid = st+(ed-st)/2; //get middle index

while (num[mid]==num[ed] && mid!=ed) {ed--;}
while (num[mid]==num[st] && mid!=st) {st++;}
if (num[mid]<num[ed] || mid==ed){  // right part ordered
res = min(res,num[mid]); //get right part min
bs(num,st,mid-1,res); //search left part
} else {  //right part unordered
res = min(res,num[st]); //get left part min
bs(num, mid+1, ed,res); //serch right part
}
}
}
int findMin(vector<int> &num) {
int n = num.size();
int res = num[0];
bs(num,0,n-1,res);
return res;
}
};


### Code(Python):

class Solution:
# @param num, a list of integer
# @return an integer
def bs(self, num, st, ed, res):
if st > ed:
return res
else:
mid = st + (ed - st)/2
while num[mid]==num[ed] and mid!=ed:
ed -= 1
while num[mid]==num[st] and mid!=st:
st += 1
if num[mid] < num[ed] or mid == ed:
res = min(res, num[mid])
return self.bs(num, st, mid-1, res)
else:
res = min(res, num[st])
return self.bs(num, mid+1, ed, res)

def findMin(self, num):
n = len(num)
res = num[0]
return self.bs(num, 0, n-1, res)


#### 1 comment:

1. time complexity? O(n) isnt it??