题目

解法：二分查找

思路

利用二分查找，通过比较中间元素与右边界元素来确定最小值所在区间。

该方法正确性的关键在于旋转数组由两个有序子数组组成，且左边子数组所有元素均大于右边。若 nums[mid] > nums[r]，则 mid 位于左侧有序段，最小值必在右侧；否则 mid 位于右侧有序段，最小值在 mid 或其左侧。每次迭代都将搜索范围减半，最终收敛到最小值。

• Step 1: 初始化左右指针 l=0, r=n-1
• Step 2: 当 l<r 时循环，计算 mid = l + (r-l)/2
• Step 3: 若 nums[mid] > nums[r]，则 l = mid + 1
• Step 4: 否则 r = mid
• Step 5: 返回 nums[l]

复杂度

• 时间复杂度: $O(\log n)$
• 空间复杂度: $O(1)$

代码

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