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.
Answer:
public class Solution {
public int findMin(int[] num) {
int start=0, end=num.length-1;
while(start+1 < end){ //ensure: start != mid != end
int mid = start + (end-start)/2;
if(num[mid] < num[end]){
end = mid;
}
else{
start = mid;
}
}
if(num[start]<num[end]){
return num[start];
}
return num[end];
}
}
No comments:
Post a Comment