[!info] related notes 算法面试题型 MOC 二分查找

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

题目

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

题目特征

• 输入非空，原数组严格升序，可旋转也可保持原顺序
• 元素互不相同
• 期望时间复杂度 O(log n)

组合起来基本就是：二分找旋转点 / 最小值。

思路

虽然数组整体不完全有序，但它可以看成：

• 左边较大的一段 + 右边较小的一段

有实际旋转时，最小值是右侧较小段的起点；未旋转时，最小值直接是首元素。两种情况都满足后面的区间不变量。

核心做法：在闭区间 [left, right] 上二分，比较 nums[mid] 和 nums[right] 来判断最小值在哪一侧。

为什么和 nums[right] 比

right 永远是当前搜索区间的最右端。

• 如果 nums[mid] < nums[right]：说明 mid..right 这段是有序的，最小值不在 mid 的右边，但 mid 可能就是最小值 => right = mid
• 如果 nums[mid] > nums[right]：说明 mid 在左边较大那段，最小值一定在右边且不包含 mid => left = mid + 1

循环不变量

• 最小值始终在 [left, right] 内
• 每次循环都缩小区间
• 最终 left == right，该位置即最小值

易错点

• nums[mid] < nums[right] 时不能写 right = mid - 1（因为 mid 可能是最小值）
• 最终返回 nums[left]（此时 left == right）
• “闭区间”不等于“机械 ±1”，更新规则取决于 mid 能否被排除
• 本例 else 依赖元素互异；带重复时 nums[mid] == nums[right] 无法确定哪侧含最小值，不能直接排除 mid

代码（JavaScript）

var findMin = function(nums) {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] < nums[right]) {
      right = mid;      // mid 可能是最小值，保留
    } else {
      left = mid + 1;   // mid 不可能是最小值，排除
    }
  }

  return nums[left];
};

复杂度

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

一句话总结

比较 nums[mid] 和 nums[right]：若 nums[mid] < nums[right]，最小值在左侧且包含 mid；否则在右侧且不包含 mid，不断收缩直到 left == right。

和 33 题的区别

• 搜索旋转排序数组：找 target
• 本题（153）：找旋转点 / 最小值（更基础、更纯粹）