手帐 Blog

主题

复盘 · LC 35 搜索插入位置（二刷） ​

题目 ​

题意 ​

有序数组 nums（无重复）与 target：若存在则返回下标；否则返回应插入的位置（插入后仍有序）。

等价于找第一个 ≥ target 的下标（lower_bound）；若都小于 target，答案是 nums.length。

涉及算法 ​

标签一句话
二分查找while (left <= right)，结束后 left 即插入位
lower_bound有序里找「第一个不小于」

教程对照：14 · 二分查找标准模板（本篇精讲题就是 35）。

评价我的解法 ​

对比 一刷 的自创夹逼，二刷已经是标准闭区间模板，循环结束 return left——这正是教程要你默写的形态，进步实打实。

我的代码（摘自 35-搜索插入位置-二刷/index.js，不含测例）：

javascript
var searchInsert = function (nums, target) {
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    console.log(left, right);

    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
      break;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return left;
};

对在哪：

  1. 模板正确：命中返回 mid；偏大收右、偏小收左；找不到时 left 落在插入位。
  2. 边界自然覆盖：插到开头（全程走右收缩）、插到末尾（left 顶到 length）都不用特判。

还糙的两点（不影响正确性，提交前应清）：

  1. 循环里留了 console.log——提交环境会拖慢，也显调试未收尾。
  2. return mid 后面的 break 是死代码，删掉即可。

小结：二刷目标达成——从「会二分意思」到「能默写 lower_bound」。这题可以标成过关，后面用 74 / 34 等变体加固。

最佳题解 ​

与你的主逻辑一致，仅去掉调试与死代码：

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] > target) right = mid - 1;
    else left = mid + 1;
  }
  return left;
};
  • 时间 O(log n)，空间 O(1)。
  • 开区间写法 left < right + right = mid 也可，二选一练熟即可，面试别混用。

关联题目 ​

题为何相关
34. 在排序数组中查找元素的第一个和最后一个位置两次 lower_bound / 边界二分
74. 搜索二维矩阵今天同专题；一维模板映射到矩阵
278. 第一个错误的版本答案二分同一骨架

一句话带走 ​

搜索插入 = 闭区间二分，结束返回 left；二刷已过关，记得交题前清掉 console.log。