Suppose an array sorted in ascending order 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.
寻找旋转排序数组最小值。最直接的办法是寻找第一个跌落点，即为最初排序数组的第一个值，返回即可。代码如下。
int findMin(int* nums, int numsSize) {
int i = 0;
if (numsSize<1){
return 0;
}
int ans = nums[0];
while (i<numsSize){
if(i>0){
if (nums[i]<nums[i-1]){
return nums[i];
}
}
i++;
}
return ans;
}
也可以利用二分的方法，判断最小值会落到哪个区间，进一步判断
int find(int *nums,int s,int t)
{
if(s==t)
return nums[s];
if(s==t-1)
{
int min=nums[s];
if(min>nums[t])min=nums[t];
return min;
}
int mid=(s+t)/2;
if(nums[mid]>nums[t])
return find(nums,mid,t);
return find(nums,s,mid);
}
int findMin(int* nums, int numsSize) {
return find(nums,0,numsSize-1);
}
将上述递归的方法转化为非递归如下：
int findMin(vector<int> &num) {
int start=0,end=num.size()-1;
while (start<end) {
if (num[start]<num[end])
return num[start];
int mid = (start+end)/2;
if (num[mid]>=num[start]) {
start = mid+1;
} else {
end = mid;
}
}
return num[start];
}
