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:
Since it is sorted array, binary search may be the hint. Let m be the middle index of array num, if num[0] < num[m], then first part is sorted, the minimum element would be either num[0] or the minimum of the second part, which can be computed recursively. Similarly, if num[m] < num[n], second part is sorted, the minimum element would be either num[m] or the minimum of the first part.
int findMin(vector<int> &num) {
int b = 0;
int e = num.size() - 1;
int minValue = INT_MAX;
while(b <= e) {
int m = b + (e- b)/2;
//it is sorted from b to m
if (num[b] <= num[m]) {
minValue = min(num[b], minValue);
b = m + 1;
}
else {
minValue = min(num[m], minValue);
e = m-1;
}
}
return minValue;
}
No comments:
Post a Comment