Leetcode 153. Find Minimum in Ro

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];
    }