Find Minimum in Rotated Sorted Array

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.

You may assume no duplicate exists in the array.

Analysis:

In a sorted array, the minimum is the first element. Now the array has been rotated, so we need to search the minimum element. Binary search is usually a efficient way dealing with such problems where the "sub" array has the similar structure of the "parent" array.

In this problem, there is only 1 rotation, so that there are only limited cases when we split the array using the mid-element:
1. the right part is ordered (A[mid] < A[ed])
2. the right  part is unordered (A[mid] > A[ed])
Some might say that what about the left part of the array? Note that there is only 1 rotation, which indicates that if right part is unordered, the left part of array must be ordered.

Considering the above two cases, finding the minimum is now becoming a simple binary search with slight modifications. Details can be seen in the following code.

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
if (num[mid]<num[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); //search 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
if num[mid] < num[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)