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

题目描述
假设一个按升序排列的数组在某个未知的旋转点进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。要求设计时间复杂度为 O(log n) 的算法，找出旋转后的数组中的最小元素。数组中不包含重复元素。

关键点分析

1. 旋转后的数组由两个有序段组成，最小元素是第二个有序段的起始点。
2. 直接遍历数组需要 O(n) 时间，但题目要求 O(log n)，提示使用二分查找。
3. 无重复元素保证了二分查找的可靠性。

解题步骤

1. 理解旋转数组的特性
旋转后的数组分为两部分：左段（较大值）和右段（较小值）。例如 [4,5,6,7,0,1,2]：

• 左段：[4,5,6,7]（所有值 ≥ 左段第一个元素 4）
• 右段：[0,1,2]（所有值 < 左段第一个元素 4）
  最小值是右段的第一个元素，其索引称为旋转点（pivot）。

2. 二分查找的思路

• 设左边界 left = 0，右边界 right = n-1。
• 比较中间元素 nums[mid] 与右边界元素 nums[right]：
  • 若 nums[mid] < nums[right]：说明 mid 在右段（较小段），最小值在 mid 左侧（含 mid），收缩右边界：right = mid。
  • 若 nums[mid] > nums[right]：说明 mid 在左段（较大段），最小值在 mid 右侧（不含 mid），收缩左边界：left = mid + 1。
• 终止条件：left == right，此时指向最小值。

3. 逐步推演示例
数组：[4,5,6,7,0,1,2]

1. left=0, right=6 → mid=3（值 7）
   • 比较：7 > 2（mid 在左段）→ left = mid+1 = 4
2. left=4, right=6 → mid=5（值 1）
   • 比较：1 < 2（mid 在右段）→ right = mid = 5
3. left=4, right=5 → mid=4（值 0）
   • 比较：0 < 2（右段）→ right = mid = 4
4. left=4, right=4 → 结束，最小值 nums[4]=0。

4. 为什么比较右边界而非左边界？

• 比较 nums[mid] 和 nums[right] 可明确判断 mid 在左段还是右段：
  • 右段恒小于等于右边界（因右段是升序）。
• 若比较左边界 nums[left]，需额外处理数组未旋转的情况（如 [0,1,2]），增加复杂度。

5. 代码实现（Python）

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

6. 复杂度分析

• 时间复杂度：每次迭代将搜索范围减半，O(log n)。
• 空间复杂度：O(1)。

总结
通过二分查找比较中间元素与右边界，可高效定位旋转点。关键思路是利用旋转数组的分段有序性，通过比较快速缩小搜索范围。