搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例

输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

我的解题过程

第一次尝试：二分查找 + 边界判断（错误）

一开始的思路是用二分查找，同时用一个 index 变量记录插入位置，最后再对边界情况做额外判断。

function searchInsert(nums: number[], target: number): number {
  let l = 0;
  let r = nums.length - 1;
  let index = 0;

  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] > target) {
      r = mid;
      index = mid + 1;
    } else if (nums[mid] < target) {
      l = mid + 1;
      index = mid + 1;
    } else {
      return mid;
    }
  }

  if (target > nums[nums.length - 1]) return nums.length;
  if (target < nums[0]) return 0;
  return index;
}

但这个方法是错误的，在某些情况下会给出错误答案：

测试用例：

输入：nums = [3,5,7,9,10], target = 8
预期输出：3
实际输出：4

问题出在哪里？

• index 的更新逻辑是错误的，在 nums[mid] > target 时更新 index = mid + 1 是不对的
• while (l < r) 不包含相等的情况，导致循环没有完全覆盖所有元素
• 边界判断无法弥补循环逻辑的问题，整体思路就有偏差

优化思路：简化二分查找

后面想明白了，其实不需要额外的 index 变量和边界判断。关键在于：把 while 的条件改成 l <= r，让循环能覆盖所有情况。

具体来说：

• 当 nums[mid] < target 时，说明目标在右半部分，l = mid + 1
• 否则（nums[mid] >= target），说明目标在左半部分或就是当前位置，r = mid - 1
• 循环结束时，l 就是答案——要么是找到的目标位置，要么是应该插入的位置

为什么 l 就是答案？因为循环结束时 l > r，此时 l 指向的就是第一个大于等于 target 的位置，正好就是插入位置。

function searchInsert(nums: number[], target: number): number {
  let l = 0;
  let r = nums.length - 1;

  while (l <= r) {
    const mid = Math.floor((l + r) / 2);

    if (nums[mid] < target) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }

  return l;
}

小结

这道题的核心是理解二分查找中 while (l < r) 和 while (l <= r) 的区别。使用 l <= r 可以让循环覆盖所有元素，循环结束时 l 自然就是插入位置，不需要额外的边界判断。

代码从第一版的多个分支判断 + 边界处理，简化到了只需要一个判断条件，思路更清晰，代码也更简洁。