Find Minimum in Rotated Sorted Array

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

分析

未旋转情况：
- 如果数组的首元素小于尾元素，说明数组未旋转，直接返回 nums[0]
二分查找旋转点：
- 在旋转数组中，最小值位于右部分的起点。
- 使用二分查找，通过比较 nums[mid] 和 nums[0] 的值，可以判断最小值的所在位置：
  - 如果 nums[mid] >= nums[0]，说明最小值在右侧，缩小左边界
  - 如果 nums[mid] < nums[0]，说明最小值在左侧或当前 mid 是最小值，缩小右边界
- 最终，r + 1 指向最小值的位置

时间复杂度

二分查找的时间复杂度为 O(logn)

空间复杂度

使用常量级额外空间，空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    int findMin(vector<int>& nums)
    {
        int n = nums.size();
        // 如果数组未旋转，直接返回首元素
        if (nums[0] <= nums[n - 1])
            return nums[0];

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1; // 取中间值
            if (nums[0] <= nums[mid])
                l = mid; // 最小值在右侧
            else
                r = mid - 1; // 最小值在左侧
        }
        return nums[r + 1]; // 返回最小值
    }
};