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

两天宇宙人

2020-02-20

😂二分查找

值得注意的是：if(nums[m] > mo) { 这行代码可以改为 if(nums[m] >= mo) {

原因是：这里不存在nums[m] == mo的情况。
例如： [3 4 5 1 2]

lo = 0 hi = 3 m = 1 A[m] = 4 > 2
lo = 2 hi = 3 m = 1 A[m] = 5 > 2

从道理上来说，是因为这里是分叉点，所以不存在相等的状况。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int mo = nums.back(),
        lo = 0, hi = nums.size() - 1, m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] > mo) {
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        return nums[lo];
    }
};