手帐 Blog

主题

复盘 · LC 35 搜索插入位置 ​

题目 ​

题意 ​

给定升序且无重复的整数数组 nums 与目标值 target：

  • 若 target 存在，返回其下标；
  • 若不存在，返回它按序插入后应在的下标。

本质是找「第一个 >= target 的位置」（lower bound）；若都更小则返回 nums.length。

边界：插到最前 / 最后、命中首尾、单元素、空数组（题目约束通常 n >= 1，本地测例仍宜考虑）。

涉及算法 ​

标签一句话
二分查找有序数组找位置 → l/r/mid，收敛到插入点
线性扫描从左扫到第一个 >= target；能过但非本题考点

教程对照：14 · 二分查找标准模板。

评价我的解法 ​

文件里留了两版：先注释掉的线性扫描，再写的二分。说明你知道本题要二分，且会先用暴力兜底——学习路径是对的。

我的代码（摘自 35-搜索插入位置/index.js 当前启用的二分版）：

javascript
var searchInsert = function (nums, target) {
  let res = 0;
  let len = nums.length;

  let left = 0;
  let right = len - 1;
  let mid = parseInt((left + right) / 2);
  if (target > nums[len - 1]) {
    return len;
  }
  if (target < nums[0]) {
    return 0;
  }
  while (left < len - 1 && right > 0) {
    if (target === nums[mid]) {
      res = mid;
      break;
    }
    if (left === right - 1) {
      res = right;
      break;
    }
    if (target > nums[mid]) {
      left = mid;
      mid = parseInt((left + right) / 2);
    } else {
      right = mid;
      mid = parseInt((left + right) / 2);
    }
  }
  return res;
};

对在哪：

  • 两端特判（小于首、大于尾）直觉正确。
  • left === right - 1 时取 right，对应「夹在两数之间插右边那格」，多数有序用例能过。

糙 / 风险在哪：

  1. 循环条件非标准：while (left < len - 1 && right > 0) 不是常见的 left <= right / left < right，不变量难口述，换边界容易挂。
  2. left = mid 不收缩：经典二分找插入点时，左侧应 left = mid + 1，右侧 right = mid（或对称模板）。你把 left 贴在 mid 上，靠「相邻就停」硬收，能撞对答案，但不像可复用模板。
  3. 空数组：nums[len - 1] / nums[0] 会读到 undefined；本地注释里有 [] 测例，这版不稳。
  4. parseInt((l+r)/2)：能用，但更常见 Math.floor((l+r)/2) 或 (l+r)>>1；大数场景还有溢出话题（JS 里较少踩）。

注释掉的线性版其实更干净：

javascript
for (let i = 0; i <= nums.length; i++) {
  if (nums[i] >= target) return i;
}
return nums.length;

（你原写法用 res + 末尾补 len，等价。）结果对、复杂度 O(n)，面试会被追问「为何不用二分」。

小结：方向选对了（要二分），实现还停在「特判 + 相邻夹逼」的自创版；需要换成教程里的标准 lower_bound 模板默写。

最佳题解 ​

找第一个 >= target 的下标：

javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0;
  let right = nums.length; // 开区间右端：允许插到末尾
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
};
  • 时间 O(log n)，空间 O(1)。
  • 为何更优：无额外特判；循环不变量清晰（[left, right) 始终是候选插入区间）；空数组自然返回 0。
  • 闭区间写法同样可：right = nums.length - 1，结束时用 left 作为插入点，命中 nums[mid] === target 可直接返回。

关联题目 ​

题为何相关
34. 在排序数组中查找元素的第一个和最后一个位置同一套边界二分（左右端点）
278. 第一个错误的版本「第一个满足条件的位置」同一模板
704. 二分查找标准存在性二分，打底

一句话带走 ​

搜索插入位置 = 有序数组里找第一个 ≥ target 的下标；默写开区间 left < right + mid 收缩，别靠两端特判硬拧。