我来给你讲解 LeetCode 第 153 题「寻找旋转排序数组中的最小值」。

题目描述

已知一个长度为 n 的升序数组，预先进行了旋转操作（例如 [0,1,2,4,5,6,7] 旋转后可能变成 [4,5,6,7,0,1,2]）。
请找出并返回数组中的最小元素。
要求时间复杂度为 O(log n)。

关键特征

• 数组元素互不相同。
• 原数组是升序的，旋转后变成两段升序的区间。
• 最小值的位置是第二段升序区间的第一个元素，它的特点是：
  • 它比前一个元素小（如果前一个元素存在的话）。
  • 它比它后面的元素都小（因为两段都是升序，且它位于第二段开头）。

思路分析

1. 暴力法（不符合要求）

直接遍历数组，找到最小值。时间复杂度 O(n)，但题目要求 O(log n)，提示我们用二分查找。

2. 二分查找的思路

旋转后的数组可以看作两部分：

• 左半段：[较大值段]，所有元素 ≥ 数组第一个元素。
• 右半段：[较小值段]，所有元素 < 数组第一个元素。
  最小值是右半段的第一个元素。

二分查找策略：
比较 nums[mid] 与 nums[high]（或 nums[0]，但比较 nums[high] 更直观）：

• 如果 nums[mid] > nums[high]：说明 mid 在左半段，最小值在 mid 右侧 → low = mid + 1。
• 如果 nums[mid] < nums[high]：说明 mid 在右半段，最小值在 mid 左侧（也可能是 mid 本身） → high = mid。
• 当 low == high 时，就找到了最小值。

逐步推导示例

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

1. 初始状态
   low = 0, high = 6
mid = (0+6)//2 = 3 → nums[3] = 7, nums[high] = 2
7 > 2 → mid 在左半段，最小值在右侧 → low = mid + 1 = 4

2. 第二轮
   low = 4, high = 6
mid = (4+6)//2 = 5 → nums[5] = 1, nums[high] = 2
1 < 2 → mid 在右半段，最小值在 mid 或左侧 → high = mid = 5

3. 第三轮
   low = 4, high = 5
mid = (4+5)//2 = 4 → nums[4] = 0, nums[high] = 1
0 < 1 → mid 在右半段，最小值在左侧或本身 → high = mid = 4

4. 结束
   low == high == 4 → 最小值 nums[4] = 0

代码实现（Python）

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

复杂度分析

• 时间复杂度：O(log n)，每次将搜索范围减半。
• 空间复杂度：O(1)，只用了几个变量。

关键点总结

• 旋转排序数组的最小值位置是右半段的开头。
• 二分时比较 nums[mid] 与 nums[high]（而不是 nums[low]），可以避免一些边界问题。
• 循环条件是 low < high，最终 low 和 high 相遇的位置就是最小值。