好的，我们来看 LeetCode 第 153 题“寻找旋转排序数组中的最小值”。

1. 题目描述

已知一个长度为 n 的升序数组，在某个未知下标 k（0 ≤ k < n）处进行了旋转，得到形如 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 的数组。
给你旋转后的数组 nums，请找出并返回数组中的最小元素。

要求时间复杂度为 O(log n)。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0

示例 3：

输入：nums = [11,13,15,17]
输出：11
解释：数组没有被旋转，仍保持升序。

2. 思路分析

2.1 关键观察

• 旋转后的数组可以看作两个递增段，左段的所有元素 ≥ 右段的所有元素，且最小值出现在右段的第一个位置。
• 如果数组没有旋转（即旋转 0 次），那么最小值就是第一个元素。
• 要求 O(log n)，提示使用二分查找。

2.2 二分查找思路

设 left = 0, right = n-1：

• 如果 nums[left] < nums[right]，说明整个区间是递增的，最小值就是 nums[left]。
• 否则，区间包含旋转点，我们取中点 mid = left + (right - left) // 2：
  • 如果 nums[mid] > nums[right]，说明 mid 在左段，最小值在 mid 右侧，令 left = mid + 1。
  • 否则（nums[mid] < nums[right] 或 nums[mid] == nums[right] 但这里无重复元素，所以 mid 在右段），最小值在 mid 或其左侧，令 right = mid（不能是 mid-1，因为 mid 可能就是最小值）。

3. 详细步骤推导

我们以 nums = [4,5,6,7,0,1,2] 为例：

初始：
left = 0, right = 6
nums[left] = 4, nums[right] = 2
4 < 2 不成立 → 有旋转，进入二分。

第 1 轮：
mid = 0 + (6-0)//2 = 3
nums[3] = 7, nums[right] = 2
7 > 2 → mid 在左段，最小值在右侧：
left = mid + 1 = 4

第 2 轮：
left = 4, right = 6
nums[left] = 0, nums[right] = 2
0 < 2 → 区间递增，最小值是 nums[4] = 0，但此时我们继续二分逻辑：
mid = 4 + (6-4)//2 = 5
nums[5] = 1, nums[right] = 2
1 < 2 → mid 在右段，最小值在 mid 或左侧：
right = mid = 5

第 3 轮：
left = 4, right = 5
mid = 4 + (5-4)//2 = 4
nums[4] = 0, nums[right] = 1
0 < 1 → 在右段，right = mid = 4

第 4 轮：
left = 4, right = 4 → 结束，最小值 nums[4] = 0。

4. 算法模板

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        if nums[left] < nums[right]:
            return nums[left]
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

5. 边界情况与解释

• 无旋转：如 [1,2,3]，一开始 nums[left] < nums[right] 成立，直接返回 nums[0]。
• 两个元素：如 [2,1]，第一次 mid=0，nums[0]=2 > nums[1]=1 → left=1，然后 left==right 结束，返回 nums[1]=1。
• 最小值在 mid 位置：如 [5,1,2,3,4]，第一轮 mid=2，nums[2]=2 < nums[4]=4，说明 mid 在右段，所以 right=2，不会错过最小值。