先别急着写代码。面试官把“二分查找”四个字抛出来的时候绝大多数人都会松一口气毕竟它看起来太简单了10个人里有9个都能在两分钟内写出一版 while 循环。但恰恰是这个看起来人畜无害的模板它在边界条件上的处理非常容易出问题一个不小心就是死循环。我这几年代码评审和面试里见过太多这样的场景候选人唰唰写完自信满满地跑测试用例结果输入换成[1, 2, 2, 2, 3]查找左侧边界程序直接卡死在 while 里光标一闪一闪空气瞬间安静。这就是二分查找的经典陷阱不是你不会写而是你没有把“边界条件”和“区间不变量”串起来理解。这篇文章我不讲虚的直接从死循环的产生根源讲起把左闭右闭、左闭右开、上取整下取整这些概念全部掰开揉碎最后给出一套可以直接抄作业的模板顺带解决你搜“二分查找死循环”时看到的一堆常见报错和面试现场翻车案例。1. 理解二分查找的设计思路为什么区间写法决定生死1.1 三种常见实现形式的差异与选择二分查找常见的实现形式有三种递归、迭代循环、封装成函数接口。面试和工程里最常用的是迭代循环因为递归每次调用都会压栈虽然代码看着简洁但边界条件一旦写错递归栈直接爆掉排查难度比循环高一个量级。递归版本大概长这样def binary_search_recursive(nums, left, right, target): if left right: return -1 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: return binary_search_recursive(nums, mid 1, right, target) else: return binary_search_recursive(nums, left, mid - 1, target)迭代版本则是把递归里的参数更新变成循环里的指针移动def binary_search_iterative(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 -1至于封装成函数接口典型的就是 PTA拼题A平台上的函数题系统给你一个排好序的线性表结构体和一个目标值让你实现查找函数返回下标。这种题表面上考的是查找逻辑实际上考的也是边界处理尤其是“找不到时返回值到底应该是 -1 还是 0”这种细节。我的建议是平时练习只用迭代版本就够了它的状态流转看得见摸得着适合用来理解区间不变量。递归版本在你真正吃透边界之前不建议作为主力写法。1.2 区间定义才是源头左闭右闭与左闭右开二分查找的代码形态千变万化但底层只有两种区间定义左闭右闭[left, right]和左闭右开[left, right)。这两个定义直接决定了三件事初始值怎么设、while 条件怎么写、指针移动时要不要加 1。左闭右闭的写法left和right都指向数组内真实存在的下标所以初始值一般是left 0, right len(nums) - 1。循环条件必须用left right因为当left right时这个位置还没有被检查过它依然是一个合法候选区间。如果用了left right就会漏掉最后一个元素的判断。左闭右开的写法right指向的是一个“取不到”的位置所以初始值一般是left 0, right len(nums)。循环条件用left right就够了因为left right时区间已经为空循环自然结束也不需要额外判断。这两种定义从数学上等价但混用就会出大事。比如你用了左闭右闭初始化却在某个分支写了right mid那mid这个已经被排除的位置会被重新拉进区间无限循环就来了。提示写二分查找前先在注释里写下“当前区间是 [left, right] 还是 [left, right)”再开始写代码。这行注释能帮你挡掉一半以上的低级错误。2. 死循环的本质区间长度为 2 时的自我复制2.1 用“区间长度为 2”的最小模型拆解死循环二分查找死循环几乎只发生在一个场景下区间长度为 2也就是right - left 1。这时候mid (left right) // 2在整数除法向下取整的情况下永远等于left。举个例子left 3, right 4mid (3 4) // 2 3。如果此时某个分支写了left mid那么新的left还是 3区间还是[3, 4]下一轮循环 mid 还是 3于是无限原地踏步。这是向下取整配合left mid的典型死循环组合。反过来如果此时分支写的是right midright会从 4 变成 3区间变成[3, 3]循环结束。所以结论很清晰在向下取整mid (left right) // 2的前提下left mid是危险操作right mid是安全操作。再看上取整版本mid (left right 1) // 2。同样在left 3, right 4时mid (3 4 1) // 2 4也就是mid right。此时如果写right mid新区间还是[3, 4]死循环。而上取整配合left mid时left从 3 变为 4区间收窄到[4, 4]循环自然结束。所以你记住一个镜像规则向下取整禁配left mid向上取整禁配right mid。只要违背这条规则区间长度为 2 时就会自我复制程序卡死。2.2 上取整 mid 公式的推导与适用场景上取整公式mid (left right 1) // 2不是凭空来的它专门用来配合“找最后一个满足条件的元素”这类问题。为什么要加 1就是为了在区间长度为 2 时把mid从left抬到right。这么说可能还是抽象我给你一个具体的例子找数组中最后一个小于等于target的下标。数组[1, 3, 5, 7]target 6答案显然是下标 2元素 5。用左闭右闭加向下取整的模板写while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return right这个版本没有死循环因为它遇到“满足条件”时是left mid 1不是left mid。拿[1, 5]区间举例left 1, right 2数组下标mid 1如果nums[1] target成立left跳到 2区间变空如果不成立right降到 0。两种路径都在收窄。但如果某道题要求“找到后不能跳过 mid 继续判断”例如要返回最后一个满足条件的元素本身而不是它的下一个位置很多人就会手滑写成left mid这时候就必须要配合上取整。所以上取整的价值在于允许你写left mid而不死循环用来解决靠右型搜索问题。3. 边界条件的实操套路终止条件与结果落点判定3.1 左闭右闭[left, right]的标准模板左闭右闭模板适合查找精确值、以及返回“插入位置”的场景代码如下def binary_search_left_closed(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 # 插入位置即第一个大于等于 target 的位置这个模板为什么找不到时返回left你可以这么理解循环结束时left right而left是从左往右逼近的最后一个位置它永远停在“第一个大于等于 target”的位置。举个例子数组[1, 3, 5]target 4手推一遍初始left 0, right 2mid 1nums[1] 3 4所以left 2下一轮mid 2nums[2] 5 4right 1循环结束返回left 2正好是第一个大于 4 的位置也就是插入位置。需要注意这个模板里三个分支都有加 1 或减 1不存在left mid这种原地踏步写法所以从结构上就杜绝了死循环。如果你要在这个模板上改逻辑核心原则是一旦某个元素被判断为不可能是答案就坚决把它排除出候选区间通过mid ± 1实现。3.2 左闭右开[left, right)的标准模板左闭右开模板天然适合找下界也就是第一个大于等于 target 的下标。它的终止条件是left right而且因为right不指向有效元素整个循环少了一次判断代码更干净def lower_bound(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这个模板有个特别好的性质当nums[mid] target时说明mid及它左边的所有元素都比 target 小不可能成为答案所以left mid 1是安全的当nums[mid] target时mid可能是答案所以right mid保留它。这里right mid配合向下取整不会死循环因为当区间长度为 2 时mid leftright被拉低到left区间收缩。这个模板能直接解决很多问题插入位置索引就是它的返回值查找第一个大于 target 的元素可以调用lower_bound(nums, target 1)仅对整数有效查找最后一个小于等于 target 的元素则是lower_bound(nums, target 1) - 1。把问题统一收敛到一个“下界函数”上比分别写五六个变体要省心得多。3.3 查找左侧边界与右侧边界的统一套路有一类问题很爱考在包含重复元素的数组里找某个值的第一次出现位置、最后一次出现位置。这时候不能只靠nums[mid] target就返回因为中间命中不代表它就是边界。找左侧边界第一次出现可以这样命中 target 时不着急返回继续把区间往左收即right mid - 1左闭右闭或right mid左闭右开循环结束后left就是第一位置。找右侧边界则反过来命中时继续往右收即left mid 1或left mid需要配合上取整。我把四个边界查询的映射关系整理成一张表查询 A 和查询 B 之间可以互相转化需求本质用 lower_bound 表达第一个 target 的位置lower_bound 本身lower_bound(nums, target)最后一个 target 的位置第一个 target 的位置前移一位lower_bound(nums, target) - 1第一个 target 的位置找第一个 target1 的位置lower_bound(nums, target 1)仅整数最后一个 target 的位置第一个 target 的位置前移一位lower_bound(nums, target 1) - 1仅整数有了这张表你根本不需要为“左侧边界”“右侧边界”各背一套模板只要把lower_bound写对其他全都能推出来。遇到非整数比如浮点数直接把 target 的“下一个值”换成 target 加上一个极小精度用同样的逻辑处理思路完全一致。4. 常见问题与排查技巧实录4.1 二分查找典型错误模式速查表我把这些年见过的二分查找错误归成六个模式每个都附上原因和修法你在报错时按表检查基本能定位错误现象根本原因修复方案程序卡死while 无限循环区间长度为 2 时left mid不前进或right mid不后退检查取整方向向下取整禁配left mid向上取整禁配right mid返回下标比预期大 1 或小 1没有区分“当前元素是否已排除”判断后明确用mid ± 1排除或者画区间图核对数组很大时mid计算溢出(left right) // 2在 Java/C 里可能越界改用left (right - left) // 2有重复值时找边界失败命中 target 后直接 return没有继续收缩区间找左侧边界命中后继续向左收找右侧继续向右收循环条件与区间定义不匹配左闭右闭用了left right漏判最后一个元素统一区间定义按定义选或找不到元素时返回错误默认值没有考虑“插入位置”语义按照模板返回 left或按题目要求明确返回 -1这张表里的第二行和第五行是 off-by-one 错误的重灾区。比如左闭右闭区间里left right时那个位置还没有被判断过如果循环条件写left right最后剩余的那个元素就会被跳过返回结果自然偏了。4.2 二分查找的现场调试方法实际调试二分查找死循环不需要什么高端工具。我最常用的一招是在循环体里临时加打印语句把每轮的left、right、mid打出来while left right: mid left (right - left) // 2 print(fleft{left}, right{right}, mid{mid}, nums[mid]{nums[mid]}) # 其他逻辑...当看到left和right连续几轮不变、mid也不变基本就是区间自我复制的死循环现场。此时停下来推演 2 个值区间只剩[i, i1]时当前分支会把mid赋值给哪个指针只要mid赋值给了“和它相等的那个端点”死循环就成立。我还习惯用最小用例做降级推演。二分查找死循环和边界错位绝大多数用[0, 1]和[0, 1, 2]两个数组就能复现。这两个数组覆盖了区间长度为 1 和区间长度为 2 的全部情况。你不用跑完整测试集把每个分支的走向手推一遍比任何静态检查都靠谱。顺便说一句搜“二分查找死循环”相关话题时偶尔会混进来一些诸如“Windows 服务更新死循环”之类的词条那是系统组件的重启循环问题跟算法没有任何关系别被带偏了。你只要掌握上面这套针对区间的调试方法二分查找本身的死循环一定能定位。4.3 PTA 函数题与面试场景中的边界坑PTA 平台上的二分查找题通常以函数接口形式出现比如给你一个已排序的线性表List L和目标值X要求返回 Position 类型的位置。这种题藏着三个共性坑。第一函数的返回值语义。题目要求“找不到返回 0”还是“找不到返回 -1”直接决定了你最后一行怎么写。PTA 的线性表下标习惯从 1 开始这和日常数组从 0 开始不一样很多人都栽在这里。第二函数的形参列表是固定的你不能在函数里重新定义一套自己的区间规则。也就是说你必须先把“区间不变量”想清楚再动手。我见过考生用左闭右开思路写 PTA 函数题但函数签名暴露的却是“下标从 1 到 Length”的左闭右闭语义两边对不上逻辑全乱。第三函数题的测试用例往往是大量随机数据如果边界出错不会立刻抛异常而是返回一个令人困惑的越界下标。这时候建议写一个小的本地测试脚本把有序数组反复插入、删除、查找用断言检查返回值是否落在合法区间内。具体做法是在循环里加assert 0 result len(nums)一旦越界立刻暴露。5. 一套可以直接抄作业的二分查找模板5.1 万能模板基于左闭右开的 lower_bound 写法下面这个模板集合是我在实际项目里长期使用的一套组合核心就一个lower_bound函数其他所有查找需求都是基于它的派生。你完全可以把这段代码直接抄到自己的工具库里def lower_bound(nums, target): 返回第一个大于等于 target 的下标。如果所有元素都小于 target返回 len(nums)。 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 # 使用示例 nums [1, 2, 2, 2, 3, 5] # 1. 精确查找 idx lower_bound(nums, 2) if idx len(nums) and nums[idx] 2: print(找到元素 2位置可能是, idx) # idx 指向第一个 2 else: print(未找到) # 2. 第一个大于等于 target 的位置 print(lower_bound(nums, 2)) # 输出 1 # 3. 第一个大于 target 的位置整数场景 print(lower_bound(nums, 3)) # 输出 4 # 4. 最后一个小于 target 的位置 print(lower_bound(nums, 2) - 1) # 输出 0 # 5. 最后一个小于等于 target 的位置 print(lower_bound(nums, 3) - 1) # 输出 3这套模板的精髓在于你只需要记住nums[mid] target时left mid 1否则right mid就永远不会写出死循环的版本。为什么因为left每次至少前进 1 步而right mid在向下取整时一定比原来的right小除非区间已经为空所以循环必然终止。5.2 模板使用的边界细节与变体适配使用这套模板时有三个细节必须留意。第一空数组的处理。lower_bound([], 5)直接返回 0符合“插入位置为 0”的语义。但如果你在外面直接拿返回值去访问nums[0]就会越界。所以调用后一定要先判断idx len(nums)尤其是精确查找时必须同时验证nums[idx] target否则无法区分“找到了”和“应该插入在这里”。第二当数组里有大量重复值时lower_bound总是返回最左边那个不小于 target 的位置也就是重复区间的左端点。如果题目要的是“任意一个等于 target 的下标”用lower_bound之后再做一次相等判断即可如果题目要的是“右端点”那就用lower_bound(nums, target 1) - 1的方式取区间的右边界。第三浮点数二分是这套模板的天然变体。浮点数的“下一个值”不能用 target 1而是改成 target 加一个极小量比如1e-9。需要特别注意浮点二分不能依靠left right精确终止因为浮点除法永远切不干净通常的做法是循环固定次数比如 100 次保证精度足够def float_lower_bound(nums, target, eps1e-9): left, right 0.0, max(nums) for _ in range(100): mid (left right) / 2 if mid target: left mid else: right mid return left浮点二分的终止条件成了“迭代次数”而不是“区间为空”。这也解释了为什么很多工程里的二分查找不是简单的 while而是带精度控制的循环整数二分的边界法则并不能原样套到浮点场景。6. 二分查找在真实场景中的扩展用法6.1 有序数组插入位置的工程落地二分查找最常见的工程场景是有序数组插入。比如你在维护一个排行榜数组新成绩来了要找到它该插入的位置让数组保持有序。直接用lower_bound返回的left作为插入点import bisect # Python 内置的 bisect 本质就是 lower_bound scores [60, 70, 80, 90] new_score 75 pos bisect.bisect_left(scores, new_score) scores.insert(pos, new_score) print(scores) # [60, 70, 75, 80, 90]Python 的bisect模块内部就是标准二分查找它的bisect_left对应我这个模板bisect_right对应右边界版本。日常开发能直接用标准库就用标准库但在面试手写环节你要能自己实现出来因为在手写场景中边界条件的处理才是考察重点。6.2 从查找精确值到查找“可行解”的思维升级二分查找真正强大的地方不只是查一个数在不在数组里而是寻找一个“可行解”的边界。比如一个常见的业务问题给定每个工单的处理时长要求把工单分成 k 组使得所有组的总时长最大值最小。这类问题表面看是分组贪心实际解法是二分答案先假设答案是 mid再用贪心验证能不能分成 k 组然后根据验证结果收缩搜索区间。这种场景下的“有序数组”并不是真的数组而是一个单调的函数值域。但二分查找的边界法则完全不变你判断 mid 是否可行可行就把区间往一半收缩不可行就往另一半收缩。核心还是区间不变量的维护以及对left、right两个指针的谨慎移动。可以说你吃透了边界条件二分查找就从“一个函数”升维成了“一种解题思想”。注意使用二分答案时验证函数必须满足单调性也就是当 mid 变大时结果只能从“不可行”变成“可行”不能来回摇摆。如果把非单调的验证函数丢进二分里结果不可预测这已经不属于边界条件能解决的问题了。7. 实操总结从背模板到理解不变量写二分查找最值钱的心法不是背下某个模板而是先定义清楚“当前区间内可能存在答案”这个不变量。我在实际项目里碰到过很多回过头来改 bug 的二分代码最终问题都出在区间语义不统一上有人初始化用左闭右开更新却用左闭右闭逻辑自然拧巴。我自己在写之前一定会先问三个问题区间是闭的还是开的循环结束的语义是什么mid 更新会不会让某个端点原地踏步这三个问题过一遍代码基本就稳了。做完之后我还习惯用三元素数组[0, 1, 2]把所有分支跑一遍分别针对每个分支推演一轮 left 和 right 的变化比任何静态检查都好使。这个内容后续还可以这样扩展把lower_bound推广到二维矩阵搜索把浮点二分用到数值计算求单调函数零点把二分答案用到资源调度问题。但不管怎么变边界条件的内核是一样的——区间不变量对了死循环就永远追不上你。