企业官网建设流程全解析

先别急着写代码。面试官把“二分查找”四个字抛出来的时候，绝大多数人都会松一口气，毕竟它看起来太简单了，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 = 4，mid = (3 + 4) // 2 = 3。

如果此时某个分支写了left = mid，那么新的left还是 3，区间还是[3, 4]，下一轮循环 mid 还是 3，于是无限原地踏步。这是向下取整配合left = mid的典型死循环组合。

反过来，如果此时分支写的是right = mid，right会从 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 = 2，mid = 1，nums[1] = 3 < 4，所以left = 2；下一轮mid = 2，nums[2] = 5 > 4，right = 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 == left，right被拉低到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 的“下一个值”换成 target 加上一个极小精度，用同样的逻辑处理，思路完全一致。

4. 常见问题与排查技巧实录

4.1 二分查找典型错误模式速查表

我把这些年见过的二分查找错误归成六个模式，每个都附上原因和修法，你在报错时按表检查基本能定位：

这张表里的第二行和第五行是 off-by-one 错误的重灾区。比如左闭右闭区间里，left == right时那个位置还没有被判断过，如果循环条件写left < right，最后剩余的那个元素就会被跳过，返回结果自然偏了。

4.2 二分查找的现场调试方法

实际调试二分查找死循环，不需要什么高端工具。我最常用的一招是在循环体里临时加打印语句，把每轮的left、right、mid打出来：

while left < right: mid = left + (right - left) // 2 print(f"left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}") # 其他逻辑...

当看到left和right连续几轮不变、mid也不变，基本就是区间自我复制的死循环现场。此时停下来推演 2 个值：区间只剩[i, i+1]时，当前分支会把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, eps=1e-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推广到二维矩阵搜索，把浮点二分用到数值计算求单调函数零点，把二分答案用到资源调度问题。但不管怎么变，边界条件的内核是一样的——区间不变量对了，死循环就永远追不上你。