手帐 Blog

主题

复盘 · LC 153 寻找旋转排序数组中的最小值 ​

题目 ​

题意 ​

原本升序数组被旋转若干次（如 [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]），元素互不相同，求最小值。

  • 要求尽量 O(log n)，即二分，不要整表扫一遍。
  • 边界：未旋转（仍全局有序）；最小值在开头 / 末尾；n = 1。

涉及算法 ​

标签一句话
二分变体看 mid 落在哪段有序，丢掉不可能含最小值的一半
旋转数组性质任意时刻，左半或右半至少一段有序

教程对照：15 · 二分变体（练习清单里就有 153）；与今天 74、35 二刷 同一条二分线。

评价我的解法 ​

思路清楚，提交到 100% 时间：若当前区间已有序则直接返回左端；否则左半有序则最小值在右，否则缩到左半（含 mid）。这是可用的旋转数组二分写法。

我的代码（摘自 153-寻找旋转排序数组中的最小值/index.js，不含测例）：

javascript
var findMin = function (nums) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[left] <= nums[right]) {
      return nums[left];
    }
    if (nums[left] <= nums[mid]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
};

对在哪：

  1. 「区间已有序 → 左端即最小」 一眼可讲，比死记「只跟 nums[right] 比」更贴语义。
  2. 左半有序时 left = mid + 1：最小值不可能在 [left, mid]（该段递增且整体仍旋转，最小值在右半）。
  3. right = mid 不丢 mid：最小值可能正好在 mid。

可收紧：

  1. 循环在题目保证有解时总会 return，但函数末尾没有兜底；面试可加 return nums[left] 更安心。
  2. 另一种主流模板是全程 while (left < right)，只和 nums[right] 比较——两种都对，选一种默写稳即可，别混边界。

小结：今天二分线里这题质量最高之一；可以当作「旋转数组找最值」的口述版留下。

最佳题解 ​

与右端比较的常见写法（同复杂度，分支更少）：

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
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]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
};
  • 时间 O(log n)，空间 O(1)。
  • 为何推荐：条件单一——mid 比右端大说明最小值在右，否则在左（含 mid）；循环不变量好背。
  • 你的写法并不差，面试任选其一，能画图说明即可。

关联题目 ​

题为何相关
33. 搜索旋转排序数组同一旋转结构，多一步「有序半区里找 target」
154. 寻找旋转排序数组中的最小值 II有重复，相等时要收缩边界
35. 搜索插入位置今天二刷的标准二分底子

一句话带走 ​

旋转数组找最小：区间已有序就取左端；否则丢掉有序且不含最小值的那一半。