聊二分查找十个有九个挂在边界上。尤其是“搜索插入位置”这道题LeetCode上编号35做的人极多但真要在面试或者PTA函数题里手写一遍能把边界条件说清楚的人并不多。所谓“二分查找搜索插入位置”核心就一句话在一个有序数组里找到 target 应该所在的下标如果 target 存在就返回它的位置如果不存在就返回它应该被插入的位置。听起来简单但实现里藏着循环条件、区间开闭、mid 计算、返回值含义四个关键抉择任何一个想当然就是死循环或者越界。这篇文章把这类问题从原理到写法完整拆一遍适合刚接触二分、或者刷题常错边界的人参考顺便聊聊实际工程和笔试里值得注意的细节。1. 搜索插入位置一道题看清二分查找的边界本质1.1 题目到底在问什么先讲清楚题面。你有一个升序排列的数组 nums比如[1, 3, 5, 6]给一个目标值 target。查一下如果 target 在数组里返回它的下标比如 target 5返回 2如果 target 不在数组里返回把它插入进去后仍然保持升序的位置比如 target 2数组变成[1, 2, 3, 5, 6]2 的下标是 1。这题跟普通二分查找唯一的差别就是“查不到时返回什么”。普通二分查找查不到通常是返回 -1而这里要返回“应该插入的位置”。很多第一次做的人会觉得多此一举但换个角度看这其实是二分查找更本质的形态要找的是“第一个大于等于 target 的元素位置”如果全都小于 target那就返回数组长度。这个视角一旦建立后面各种变体就都好理解了。顺带说个题外话PTA 和很多OJ上会把这类题包装成函数题只让你补一个searchInsert函数。函数题最坑的一点是主函数已经写好你看不到完整调用上下文容易想当然地返回mid结果在 target 不存在的用例上直接挂掉。整体逻辑和手写完整代码没有区别但返回值必须想清楚。1.2 为什么直接遍历不行有人会问数组都给了直接从头扫一遍比较大小第一个大于等于 target 的位置不就是插入位置吗复杂度 O(n)代码简单不烧脑为什么非要二分原因是数据规模。在笔试题里数组长度可能到10^5、10^6如果只查一次O(n) 确实也能过但如果查 m 次总复杂度 O(m*n)很容易超时。二分查找的意义就是把单次查找降到 O(log n)这是数量级的差异。举个具体例子数组长度 100 万线性查找最坏要比较 100 万次二分查找最多 20 次。20 和 1000000 的差距不需要我多解释。更重要的是二分查找是很多复杂算法的基础模块。矩阵二分、二分答案、树上倍增里都有它的影子。搜索插入位置恰好是理解和记忆二分框架的最佳载体因为它的返回值天然就是“二分查找结束后的 left 值”学懂这一题等于把二分边界问题打通了大半。1.3 二分查找的三个关键边界变量写任何二分心里都要有这三个东西区间定义你维护的查找区间是[left, right]还是[left, right)这决定了循环怎么写、mid 怎么取、边界怎么收缩循环条件区间非空才继续查left right对应左闭右闭left right对应左闭右开返回值循环结束那一刻left 或者 right 到底指向什么位置。我把这三件事叫“二分三问”。每次写代码前先在心里回答完三问再动手指。绝大多数边界错误都是三问里有一问没想清楚就开写了。接下来就以最常见的左闭右闭写法为例一步步推。2. 从零推导左闭右闭写法2.1 循环不变量先定区间规则写代码前必须确立“循环不变量”。我接下来用的区间是[left, right]也就是说在整个循环过程中target 如果存在只可能出现在这个闭区间里而且我维护的是一个“始终包含答案”的区间。这个不变量是整个推导的地基。初始化时left 0right len(nums) - 1区间覆盖整个数组没问题。循环条件用while left right因为left right时区间里还有一个元素仍然需要检查。mid left (right - left) // 2注意不要直接用(left right) // 2在 Python 里问题不大但在 C/Java 里 left right 可能溢出整型上限这是一个容易被忽略的坑。每次拿nums[mid]和 target 比较只有三种情况分别处理。重点是处理完以后新的区间依然满足“target 如果存在必定在里面”。2.2 三种情况的移动策略假设当前nums[mid]的值和 target 进行比较nums[mid] target找到了直接返回 mid这是最简单的情况nums[mid] target说明 target 在 mid 的右边mid位置以及它左边所有元素都可以排除所以left mid 1nums[mid] target说明 target 在 mid 的左边mid位置以及它右边所有元素都可以排除所以right mid - 1。核心逻辑就是这三行难的是循环结束之后返回什么。循环结束意味着区间[left, right]为空即 left 已经大于 right。此时 left 指向的位置恰好就是“第一个大于等于 target 的位置”也就是插入位置。所以答案return left。为什么 left 恰好是插入位置可以这样想循环过程中我们始终保持“left 左边所有元素都小于 targetright 右边所有元素都大于等于 target”。当区间为空时left 和 right 交错left 停在了第一个大于等于 target 的元素位置或者数组末尾如果所有元素都小于 target。这个位置正是插入后仍有序的位置。2.3 返回值的含义与选择这里有个初学者常见的困惑为什么不能return right 1其实在左闭右闭写法里left right 1所以return right 1和return left是一个意思。写 left 只是因为语义更直观逻辑上也统一。如果题目要求你“找不到就返回 -1”那就不能直接返回 left 了要在循环里判断查不到就return -1。我见过很多人在上述模板里套一层 -1 逻辑反而写错。要区分清楚搜索插入位置和普通查找的返回值语义不同模板也不该硬套。脑子里要分两条线普通查找的模板返回 mid 或 -1搜索插入位置的模板返回 left。想清楚这个区分比背十遍代码都有用。参考代码Pythondef searchInsert(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return left这段代码提交 LeetCode 35 能直接过效率是 O(log n)空间 O(1)。但通过只是起点看懂为什么 left 是对的才算真正掌握。3. 常见写法对比左闭右开还是左闭右闭3.1 四种写法逐行分析把二分写法展开其实不止两三种。网上流传最广的除了我刚才写的左闭右闭还有左闭右开。两者都能 AC面试官也不会强制你用哪一种但你自己必须讲得清楚。左闭右开的核心是初始化right len(nums)循环条件while left right区间为[left, right)也就是说 right 本身不参与检查它是一个“开边界”。此时 mid 的计算方式不变但比较后的收缩规则变成nums[mid] targetleft mid 1nums[mid] targetright mid。注意这里我把相等和大于合并了因为左闭右开写法要找的其实是“第一个大于等于 target 的位置”一旦nums[mid] targetmid 本身可能是答案不能直接排除所以 right 收缩到 mid而不是 mid - 1。循环结束时left right返回 left 即可。这段代码长这样def searchInsert(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left两种写法对同一个测试用例结果一致但对边界情况的处理有微妙差别。左闭右开写法把 target归入右边界收缩天然适合求下界左闭右闭写法三分支清晰适合普通查找。我个人的建议是二选一作为主力模板但至少要能看懂另一种因为很多开源代码里两种风格都存在读别人代码时得快速识别它用的是哪套规则。3.2 模板取舍与心法选哪个作为主力我的体会是面试场景下左闭右闭更好讲。因为它三分支很直观等于、小于、大于跟人脑的直觉一致。在竞赛或者刷题场景很多人喜欢左闭右开因为配合 C 的迭代器语义更自然STL 的lower_bound就是这种逻辑。没有绝对优劣关键是你对选定的那套规则有肌肉记忆。给一个判断口诀右边界取不取元素决定了 while 里写不写等号也决定了收缩时是否要减一。右边界取元素左闭右闭循环写收缩写right mid - 1右边界不取元素左闭右开循环写收缩写right mid。这个口诀应对绝大多数二分变体都成立。另外提一句 C、Java 里常见的溢出陷阱。left right如果都接近2^31相加会溢出所以一律用left (right - left) / 2。Python 整数无上限但为了习惯统一我也建议写成left (right - left) // 2这样在不同语言之间切换代码时不用刻意改。4. 实操中踩过的坑与排查技巧4.1 死循环是怎么来的二分死循环几乎都出在收缩规则上。最常见的一种错误写法是循环while left right但收缩时写成left mid。如果区间只有两个元素比如left 0, right 1mid 计算出来是 0如果nums[mid] targetleft 更新成 0区间变成[0, 1)一点没变死循环。这里要理解为什么left mid 1是安全的因为nums[mid] target时mid 位置已经被排除mid 1 才是最左边可能的位置不会漏答案。同理right mid在左闭右开是安全的因为 right 本身不参与检查更新成 mid 不会把 mid 漏掉。而左闭右闭里要排除 mid就必须right mid - 1。一旦混用比如左闭右开配right mid - 1可能把答案跳过左闭右闭配right mid则可能死循环。遇到死循环不要靠读代码猜直接在纸上模拟一个长度为 2 或 3 的数组手动走两轮立刻能看出来区间是不是卡住了。我在实际调试时习惯在每个循环末尾打印 left、right、mid 三者的值几乎一眼定位。4.2 越界的隐蔽场景数组越界也是二分高频报错。常见场景是目标值大于数组中所有元素此时在左闭右闭写法里循环结束后 left 等于 len(nums)nums[left]就是越界。如果你在循环外面补一句return nums[left]或者用 left 去nums[left]做比较必挂。正确姿势是插入位置就是数组末尾这个位置不要求你去访问 nums[left]直接返回 left 本身。很多初学函数题的同学看到返回值总觉得要“给一个具体下标对应的元素”在这种边界用例上想当然反而错了。记住这道题返回的是下标不是元素值越界下标也可以合法返回前提是你别去访问它。另一个隐蔽问题是输入数组为空nums []。左闭右闭写法里right -1循环直接不执行返回 left 0这个结果是正确的空数组插入 target 的位置就是 0。但如果你在代码开头写了if not nums: return 0也没错只是多余。4.3 面试中的加分细节面试官问二分通常不看你能不能写对而是看你遇到边界问题时的反应速度。我总结几个容易加分的点能主动说出right len(nums)和right len(nums) - 1的初始值差异说明你理解区间开闭能解释为什么mid用left (right - left) // 2说明你了解溢出问题能把“搜索插入位置”和 C 的lower_bound对应起来说明你有工程知识储备能在写完代码之后主动补一个 target 小于所有元素、target 大于所有元素、数组只有一个元素的测试用例说明你有测试意识。这些点加起来的印象分绝对比“背模板背得滚瓜烂熟”高很多。我面试别人的时候最怕的不是候选人写错而是候选人写完代码只盯着用例能不能过完全讲不出边界行为。二分恰恰是考察这种思维深度的好题目。5. 延伸二分答案与库函数对照5.1 从搜索插入位置到二分答案学完搜索插入位置很多二分答案类题目其实只是它的变体。所谓二分答案就是“在答案区间上做二分查找”每猜一个答案判断它是否可行然后根据判断结果收缩区间。典型题包括求数组里第 k 大的数、求最小可行值、分段数组的最大最小值等。为什么说搜索插入位置是二分答案的心理起点因为它的返回值本身就具备“第一个满足条件的点”这种语义。二分答案也有类似的语义找到第一个“可行”的位置或者最后一个“可行”的位置。你能熟练转换 left、right、mid 的语义就能迁移到这些题目上。反过来如果搜索插入位置的边界还没想透就去做二分答案大概率会在判断条件和收缩规则里栽跟头。我给一个过渡练习建议先做 LeetCode 35再做 LeetCode 34在排序数组中查找元素的第一个和最后一个位置、LeetCode 704二分查找、LeetCode 69x 的平方根。这几道加起来基本覆盖二分的全部基本套路。其中 34 题会逼你写出两个二分找左边界和找右边界正好用得上搜索插入位置的同款框架。5.2 上下界问题与库函数对照工程上Python 有现成的bisect模块其中bisect_left做的事和搜索插入位置完全一样返回数组中第一个大于等于 target 的位置。C 的 STLlower_bound同理。刷题可以用这些库函数但要慎用因为笔试题考的就是你手写的能力库函数只在验证思路时有用。.bisect_left的返回值语义跟我们的 left 完全一致所以你可以用它来对拍验证自己的手写代码是否正确。举个例子import bisect # 随机生成数组和目标对比 searchInsert 返回值和 bisect_left这个方法我几乎每次写二分变体都会用比自己肉眼盯代码快得多。对拍通过之后再提交心理踏实很多也能避免一些自以为正确实则边界有误的写法。注意对拍时不要只测随机数据固定测几个极端用例target 小于首元素、target 大于尾元素、数组长度为 1、数组为空。这才覆盖完整。写到这里搜索插入位置这道题从原理、模板、坑点到延伸应该都讲透了。我个人习惯是把return left这个结论当成二分查找“查不到答案时”的默认返回值因为它在多数变体题目里都通用。你如果刚开始学二分建议把左闭右闭和左闭右开两套代码分别手写三遍再用随机数据对拍验证半个月内边界问题基本不会再困扰你。以后看到任何二分题先把区间开闭、循环条件、收缩规则三件事写清楚剩下的就是机械执行了。