35. 搜索插入位置#

今天我想和大家聊一道特别适合入门的算法题 - LeetCode 35「搜索插入位置」。这道题虽然看起来简单，但它蕴含了二分查找的精髓，是我最喜欢用来教学的题目之一。

📚 从图书馆说起#

想象你在图书馆整理书架。手里有一本新书要插入已经按编号排序的书架中。你会怎么做？相信大多数人不会从头到尾一本本对比，而是会先看看中间的书，判断新书应该放在左边还是右边，这样反复几次就能找到正确的位置。

这正是二分查找的思想，也是我们今天要解决的问题！

问题描述#

题目目标#

给定一个升序排列的整数数组 nums 和一个目标值 target ，在数组中查找目标值。如果目标值存在，返回它的下标；如果不存在，返回它应该按顺序插入的位置。

示例 1#

输入： nums = [1,3,5,6], target = 5 输出： 2 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题解析#

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

示例：

// 示例1：目标值在数组中
// 输入: nums = [1,3,5,6], target = 5
// 输出: 2（因为 5 正好在下标 2）

// 示例2：目标值不在数组中
// 输入: nums = [1,3,5,6], target = 2
// 输出: 1（因为 2 应该插入到下标 1）

java

🤔 思路发展历程#

让我们看看解决这个问题时，思维是如何逐步进化的：

1. 最直观的思路（新手常用）#

// 从头到尾遍历一遍
for (int i = 0; i < nums.length; i++) {
    // 一旦遇到第一个大于等于 target 的位置，
    // 该位置就是 target 已存在的位置，或应插入的位置
    if (nums[i] >= target) {
        return i;
    }
}
// 如果所有元素都小于 target，则应插入到数组末尾
return nums.length;

java

这种方法虽然直观，但时间复杂度是O(n)，没有利用数组已排序的特性。

2. 二分查找思路（进阶方案）#

既然数组已经排序，我们可以用二分查找将时间复杂度降到O(log n)。

🚀 优雅的解决方案#

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0; // 左边界：当前搜索区间的起点下标
        int right = nums.length - 1; // 右边界：当前搜索区间的终点下标

        // 边界情况：如果目标值比最后一个元素还大，
        // 说明它只能插入在数组末尾
        if (target > nums[right]) {
            return nums.length;
        }

        // 在闭区间 [left, right] 内进行二分查找
        while (left <= right) {
            // 计算中间下标 mid，写成这种形式可以避免 (left + right) 溢出
            int mid = left + (right - left) / 2; 

            // 情况1：正好找到目标值，直接返回其下标
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                // 情况2：中间值小于目标值，目标只可能在右半区
                left = mid + 1;
            } else {
                // 情况3：中间值大于目标值，目标只可能在左半区
                right = mid - 1;
            }
        }

        // 循环结束表示未找到 target。
        // 此时 left 恰好停在“第一个大于 target 的位置”，就是应插入的位置
        return left;
    }
}

java

📝 代码详解#

让我们一步步理解这个解法：

1. 初始化#

left和right指针分别指向数组的开始和结束
先处理特殊情况，如果目标值比所有元素都大

2. 二分查找过程#

每次取中间位置mid
比较nums[mid]和target：
- 相等：找到目标值，直接返回
- nums[mid]小于target：说明目标在右边
- nums[mid]大于target：说明目标在左边

3. 返回插入位置#

循环结束时，left就是正确的插入位置
无需特别处理，因为left自然会停在正确位置

🎯 易错点分析#

边界条件
- while循环的条件是 left <= right 而不是 left < right
- 这确保了不会漏掉任何一个位置
中间位置计算
- 使用 left + (right - left) / 2 而不是 (left + right) / 2
- 避免整数溢出的隐患
返回值选择
- 最后返回left而不是right
- left自然停在插入位置，而right总是在其左边

💡 举一反三#

这道题的思路可以应用到很多类似场景：

查找第一个不小于目标值的位置
- 这就是我们这道题的本质
查找最后一个不大于目标值的位置
- 只需要稍微改变一下判断条件
在排序数组中查找元素的第一个和最后一个位置
- LeetCode 34题，是这道题的进阶版

🌟 面试技巧#

理解二分查找的本质
- 不是简单的查找，而是在查找的过程中缩小范围
- 每次都能排除一半的搜索空间
处理边界情况
- 数组为空
- 目标值在数组范围之外
- 数组中有重复元素
代码优化
- 考虑代码的简洁性和可读性
- 处理好整数溢出问题