欢迎阅读 欢迎来到「搜索插入位置」题解之旅本文将带你从在一列有序数字中找一个数的家这一直观场景出发深入理解二分查找边界模板的巧妙运用并掌握如何用右边界收敛模板定位插入点来返回目标值应处的位置。在开始之前建议你先了解题目背景这是 LeetCode 35 题给定升序数组nums和target若target存在则返回其下标否则返回按序插入后应有的下标。本质上插入位置就是第一个 ≥ target 的位置问题转化为二分定位边界点。明确学习目标掌握上取整 mid 的右边界模板理解收敛点语义与三种情况的分类判断并熟练处理目标小于全部或大于全部等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,3,5,6]target 5输出2target 2输出1。本文将从问题转化、右边界收敛、三分支判断、返回结果到代码实现层层递进。即使你对二分边界还不熟悉我们也会从找到最后一个不大于它的数再往后一位就是家这一直觉出发让你轻松抓住核心思想——收敛到最后一个 ≤ target前驱后一位即答案。现在让我们一起收敛区间找到 target 的插入位置吧 一.题目35. 搜索插入位置 - 力扣LeetCode二.做题思路一、问题分析前置分析题目要求在升序数组中查找target存在返回下标不存在返回插入后的下标保持有序。关键约束数组升序target可能不存在插入位置范围是[0, n]可插到末尾。核心思路插入位置 第一个 ≥ target 的位置本题采用最后一个 ≤ target 的位置 1等价思路用二分收敛到一点后分类判断。二、算法策略右边界收敛二分 分类判断核心步骤初始化区间left 0、right n - 1。右边界收敛循环while (left right)mid上取整left (right - left 1) / 2若nums[mid] target则right mid - 1否则left mid。循环结束后left是最后一个 ≤ target 的位置。分类判断nums[left] target→ 返回left恰好命中nums[left] target→ 返回lefttarget 小于所有元素插入到 0nums[left] target→ 返回left 1插入到其后。返回结果。示例执行过程nums [1,3,5,6]target阶段leftrightmidnums[mid]操作结果5①03255 5 否left2收敛5②23366 5right2退出5判断2——nums[2]5返回 222①03255 2right1收敛2②01133 2right0退出2判断0——nums[0]1 2返回 117收敛33—nums[3]6 7返回 440收敛00—nums[0]1 0返回 00四个目标分别返回2、1、4、0与题目示例完全一致。三、正确性说明简单版本收敛点语义明确循环不变量是答案一定在[left, right]内nums[mid] target时答案在左半含更小者nums[mid] target时保留 mid 向右找最后一个 ≤ target者区间单调收敛到该点不会漏解。上取整保证终止left mid向右收缩需要 mid 严格大于 left上取整在相邻区间时 mid 取 right区间必然缩小不会死循环。三分支覆盖全部收敛点与 target 的关系只有等于、大于、小于三种分别对应命中、插入到 0、插入到其后覆盖所有情况不会漏分支。无解即插入题目语义下未找到等价于插入不存在真正的无解故无需 -1 分支。四、实现细节边界防护初始化left 0、right n - 1。边界防护题目保证n 1若需健壮性可在开头加if (n 0) return 0;防止nums[0]越界循环退出后left right统一用nums[left]判断。复杂度时间 O(log n)二分收敛空间 O(1)仅常数个变量。关键判断if (nums[mid] target) right mid - 1; else left mid;右边界收缩、nums[left] target/ target/ target三分支返回。五、返回值目标映射返回left或left 1target 的下标或插入位置范围[0, n]对应题目存在返回下标不存在返回插入位置。三.代码class Solution { public: int searchInsert(vectorint nums, int target) { int n nums.size(); int left 0; int right n - 1; // 1. 右边界收敛二分找“最后一个 target”的位置 while (left right) { // mid 上取整配合 left mid 向右收缩防止相邻区间死循环 int mid left (right - left 1) / 2; if (nums[mid] target) { right mid - 1; // 目标在左半丢弃右半含 mid } else { left mid; // nums[mid] target保留 mid向右收敛 } } // 循环结束后 left right为“最后一个 target”的下标 // 2. 分类判断收敛点与 target 的关系决定答案 if (nums[left] target) { return left; // 恰好命中返回该下标 } else if (nums[left] target) { return left; // target 小于所有元素插入到最前left 恒为 0 } // nums[left] target插入到收敛点之后一位 return left 1; } };四、易错点分析难点1mid 必须上取整配合 left midint mid left (right - left 1) / 2; if (nums[mid] target) right mid - 1; else left mid;收缩分支含left mid向右保留 mid。当区间只剩相邻两个元素right left 1时若 mid下取整会取到 leftleft mid不改变 left死循环。上取整保证此时 mid 取 right区间必然缩小。取整方向必须与收缩方向匹配——这是 34/35 系列共用的核心陷阱。难点2循环条件left right与收敛点语义while (left right)本模板的语义是把区间收敛到唯一一个点退出时left right这个点就是最后一个满足 nums[i] target 的位置。若误用 704 的left rightleft right时 mid leftleft mid使区间不再缩小直接死循环。两套模板的条件与更新必须成套使用不可混搭。难点3三分支分类的语义辨析if (nums[left] target) return left; else if (nums[left] target) return left; return left 1;注意等于与大于都返回 left因为插入位置在两种情况下都是 left命中时占住该位小于全部元素时插到首位此时 left 恒为 0。只有nums[left] target收敛点在 target 之前才返回left 1。理解收敛点语义才不会把三种情况写错且可以进一步合并为if (nums[left] target) return left;。五、流程图 闭幕 恭喜你完成了「搜索插入位置」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题采用右边界收敛二分找“最后一个 ≤ target”的位置。请问为什么用右边界收敛保留mid向右靠而不是左边界收敛保留mid向左靠如果改用左边界收敛代码应如何调整当nums[mid] target时执行right mid - 1否则执行left mid。为什么当nums[mid] target时保留mid即left mid而不是left mid 1如果改成mid 1会丢失什么信息循环结束后left right此时用nums[left]与target比较分三种情况。如果target小于数组中所有元素收敛点会是哪个位置代码中的三个分支哪个会被触发延伸挑战如果数组是降序排列的查找插入位置的二分逻辑应如何调整如果题目要求返回插入位置的同时还要返回是否找到 target即若存在则返回{true, index}不存在则返回{false, index}你的代码应做哪些改动如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案选择右边界收敛是为了找到“最后一个 ≤ target”的位置便于后续判断插入位置若改用左边界收敛找“第一个 ≥ target”代码需改为nums[mid] target时left mid 1否则right mid最后返回left即可无需额外分类。保留mid是因为我们要找的是“最后一个 ≤ target”的位置mid可能是该位置的候选若直接跳到mid1会跳过可能的正确插入点。若target小于所有元素二分过程中nums[mid] target始终为真导致right不断左移最终收敛到left0nums[0] target触发return left即 0正确。延伸挑战答案挑战1降序数组中将比较逻辑反置nums[mid] target时right mid - 1nums[mid] target时left mid其余取整和收敛逻辑不变。挑战2只需新增一个bool found (nums[left] target)返回时用pairbool, int或自定义结构体即可分类逻辑保持不变。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨