LeetCode 153. 寻找旋转排序数组中的最小值

LeetCode 153. 寻找旋转排序数组中的最小值

思路：

返回最小的数实际上就是返回比nums[0]小的第一个数，

数组中数字的划分是这样的，所以我们可以用二分来找到target，如果nums[mid] < x 说明target在左半区间，否则在右半区间。

通过这道题我们也可以得出一个结论，二分算法不一定要求数组是严格单调的，只要满足某种性质就可以二分。

代码：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(nums[0] < nums[n - 1]) return nums[0];
        int x = nums[0];
        int l = 0,r = n-1;
        while(l<r){
            int mid = (l + r )>>1;
            if(nums[mid] < x) r = mid;
            else l = mid + 1;
        }
        
        return nums[r];
    }
};