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

难度：🟡 Medium | 标签：二分查找 | 状态：⬜ LeetCode 链接

思路

跟 nums[r] 比较：

• nums[m] > nums[r] → 最小值在右半（去 m+1）
• 否则在左半（含 m）

代码

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

复杂度

• 时间 O(log n)，空间 O(1)

易错 / 回顾

• 必须跟 r 比，不能跟 l 比（未旋转时 l ≤ m 一直成立）
• r = m 不是 m - 1（m 自己可能是最小）
• 含重复版（154）要在 nums[m] == nums[r] 时 r—