如果把所有算法排个"看着最简单"的榜单，二分查找（Binary Search）一定名列前茅。翻开任何一本入门教材，它的描述只有一句话：排好序的数组里，每次和中间元素比一下，砍掉不可能的那一半，重复到找到为止。 一个会写 if 的大一学生，10 分钟就能在白板上"画出"它。Computerphile 这条由 Robert Miles 博士主讲的视频，正是用 18 分钟把这套直觉讲得清清楚楚——简洁、优雅、对数级复杂度 O(log n)，堪称算法界的"abc"。
但这条视频真正值得做深度解读的，恰恰是它表面温柔之下藏着的那个反常识内核：这个"人人都会"的算法，几十年来几乎没人第一次就写对。 不是初学者，是职业程序员；不是偶尔，是系统性地写错；而且错的方式极其隐蔽——错的版本能编译、能跑、能通过几乎所有测试，却在某个临界点上悄悄崩掉。最戏剧性的一次，是同一段错误代码在 Java 标准库里潜伏了整整九年，被全世界数以亿计的程序调用，直到它的原作者自己公开认错。
这不是一个"科普小知识"，而是一面照妖镜：它照出的是整个软件工程行业对"简单"的迷信，以及一种被严重低估的工程美德——不变量推理（invariant reasoning）。本文会拆解这个 bug 到底错在哪、为什么潜伏这么久、它如何蔓延到几乎所有主流语言，以及它对今天每一个写代码的人（包括用 AI 写代码的人）意味着什么。
| 项目 | 内容 |
|---|---|
| 视频标题 | Binary Search Algorithm — Computerphile |
| 频道 | Computerphile（University of Nottingham 出品，主讲 Dr. Robert Miles，频道订阅约 260 万） |
| 时长 | 18 分 34 秒 |
| 播放量 | 约 18.1 万次（截至检索日） |
| 发布时间 | 约 2018 年（Computerphile 经典讲解视频） |
| 核心主题 | 二分查找的原理、对数复杂度，以及它"看似简单实则极易写错"的陷阱 |
Robert Miles 的讲解非常友好。他从一个朴素问题切入：在字典里查一个词，你绝不会从第一页翻到最后一页，而是直接翻到中间，判断目标在左半边还是右半边，再继续对半砍。这就是二分查找的物理直觉。接着他用数学点破关键：一个长度为 n 的有序数组，每砍一次剩余量减半，所以最多只需要 ⌈log₂(n)⌉ 次比较。100 万元素？约 20 次。10 亿元素？约 30 次。这是把"线性翻找"的 O(n) 直接压成 O(log n) 的指数级提速，也是为什么从数据库索引、std::lower_bound 到 Git 的对象查找，底层几乎都是它。
视频的后半段开始亮出刀子：他现场写了一段二分查找，然后指出——循环条件到底写 low < high 还是 low <= high？中点是 (low + high) / 2 还是 low + (high - low) / 2？边界到底是 high = mid - 1 还是 high = mid？这些看似吹毛求疵的细节，每一个都可能让程序在某个特定输入下死循环、越界或漏掉答案。这是视频留给观众的真正钩子，也是本文要深挖的主线。（以上为视频原观点的转述）
要理解二分查找为什么这么坑，必须回到算法史上一桩著名的"翻车现场"。1986 年，贝尔实验室的 Jon Bentley 在《Programming Pearls》（编程珠玑）这本书/专栏里，给一群职业程序员布置了一个任务：在白纸上手写一个正确的二分查找，时间是两小时。结果令人震惊——绝大多数人都写错了，能写出完全正确版本的只有约 10%。
这不是实习生，是资深工程师；不是不能跑，而是边界条件、终止条件、下标更新总有至少一处暗伤。Bentley 据此得出一个被反复引用的结论："简单"是个心理学陷阱。算法的描述越短、越直觉，人就越倾向于凭感觉写，而不是凭逻辑证明它对。更讽刺的是，Bentley 自己在书里给出的"标准答案"版本，本身也是错的——而这个错误，又偷偷传给了下一代人。这段延伸背景来自 Bentley 的经典著作，视频里点到为止，本文展开。
Bentley 书里、以及绝大多数教科书和早期工业代码里的二分查找，求中点都是这么写的：
mid = (low + high) / 2;
它看起来天衣无缝：两数之和除以二，取中点。问题藏在 low + high 这一步。在 C、C++、Java 这类语言里，整数是定宽的，Java 的 int 上限是 2³¹ − 1 ≈ 21.4 亿。当一个数组足够大，low 和 high 都在十亿量级时，low + high 会悄悄溢出成一个负数，于是 mid 变成一个负的下标，紧接着就是数组越界、崩溃，或者更阴险的——返回一个错误的位置而不报错。
正确的写法是避开求和、改用差值：
mid = low + (high - low) / 2; // C/C++ 通用安全写法
Java 里还可以利用无符号右移：
mid = (low + high) >>> 1; // >>> 是无符号右移，溢出也被当成大正数处理
这看起来是个微不足道的语法差异，但它正是那个"潜伏九年"的 bug 的全部技术内核。（本节为基于公开 CS 文献的延伸分析）
故事在 2006 年达到高潮。这一年的 6 月 2 日，Google 的 Joshua Bloch——他本人就是 Java 标准库里 Arrays.binarySearch 的作者——在官方研究博客上发了一篇震动工程圈的文章，标题相当炸裂：
《Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken》 （号外号外：几乎所有的二分查找和归并排序都是坏的）
Bloch 坦白：他从 Bentley 书里忠实抄来的那段代码，带着那个加法溢出 bug，从 1997 年 Java 1.2 起就一直躺在 JDK 里，被全世界无数 Java 程序调用，长达约九年。Bug 编号 5045582。同一处错误还出现在 Java 的 Arrays.mergeSort 里。最让 Bloch 后怕的是：它不是"偶尔崩溃"，而是一颗哑弹——只有当数组大到上亿元素时才会引爆，所以日常测试一个都抓不到。
Bloch 在文末留下了那句被工程师们传颂至今的话：大意是——"这段代码我读了无数遍，写过无数遍，从来没看出毛病。"原作者尚且如此，可见这不是眼力问题，而是方法问题。这段历史来自 Bloch 2006 年的博客与 Java bug 数据库，是本文最重要的延伸事实。
这个 bug 的可怕之处，不在于它有多复杂，而在于它完美地躲在了所有常规测试的射程之外。要触发溢出，数组必须超过约 2³⁰（约 10.7 亿）个元素。在 1990 年代甚至 2000 年代初，这种规模的内存数组几乎不存在——单机能装下这么多元素本身就是奢望。所以每个跑过的单元测试、每个集成测试、每个生产环境，输入规模都远在阈值之下，bug 自然"一直工作得很好"。
是大数据时代把这颗哑弹点着了：内存便宜了、JVM 堆大了、单进程动辄处理几十亿元素，溢出终于开始偶发崩溃。这是一个关于"测试覆盖率"的深刻教训：100% 的行覆盖率，完全不等于 100% 的正确性。 真正的边界，藏在数据类型的取值范围里，而不在你能想到的用例里。视频没有展开这点，但它是理解"为什么九年没被发现"的钥匙。
如果把溢出 bug 修了，二分查找就稳了吗？远没有。Robert Miles 在视频后半段演示的那些纠结——< 还是 <=、mid 还是 mid-1、mid+1——暴露的是同一个根因：大多数人写二分查找靠的是"砍一半"的直觉，而不是"循环不变量"的证明。
正确的工程姿势是先定义不变量。比如要找第一个 >= target 的位置（即 C++ std::lower_bound 的语义），那么循环里必须始终保证：答案一定落在闭区间 [low, high] 内。每一次更新 low = mid + 1 或 high = mid，都要能证明这个不变量不被破坏。一旦你用不变量来推导，所有那些"< 还是 <="的纠结会自动消解——因为它们是不变量的逻辑推论，不是要靠"经验"去猜的玄学。
本文的核心观点：二分查找之所以难，不是因为它复杂，恰恰是因为它"看起来太简单"，诱使人放弃不变量推理、退回直觉。溢出 bug 只是这种退让最著名的一个症状。
Bloch 的文章像一颗石子，激起整个工业界的自检浪潮。人们回头去查各家标准库，发现同样的加法溢出在很多语言里都有过——C++ 标准库的某些实现、.NET 的早期版本、不少教科书示例，或多或少带着这个暗伤。一时间"你的二分查找真的对吗"成了工程师社群的热门话题。
更值得今天的我们警觉的是：这个 bug 并没有因为"大家都知道"而消失，它只是换了宿主。 近年不少针对大语言模型代码生成能力的评测里，二分查找（以及它的变种 lower_bound/upper_bound）依然是高频翻车点——模型能写出"看起来很对"、能通过样例、却在边界上死掉的版本。原因和 1986 年那批程序员一模一样：它在模仿"二分查找长什么样"，而不是在推理"它为什么正确"。 这也是为什么二分查找至今仍是顶级公司面试和正确性基准测试的常客——它是一块廉价却精准的"不变量推理"试金石。
最后补一个视频没提、但极有启发性的尾声。既然二分查找这么坑，有没有可能用数学"证明"一个实现对不对？答案是：可以，而且真的有人这么干了。2015 年前后，形式化方法（formal methods）社区用定理证明工具对 Java 标准库里的排序和查找算法做过严格验证，最著名的是 de Gouw 等人对 TimSort 的验证——结果还真在用了近十年的工业级排序算法里挖出了真实的越界 bug（这是另一个"潜伏多年"的故事，可窥见这一类问题之普遍）。对二分查找这类小而关键的算法，形式化验证已经能给出"机器证明级别的正确性保证"。这给我们的启示是：对于"简单到不值得测"的核心算法，证明有时比测试更便宜、更可靠。
flowchart TD
A["二分查找 Binary Search<br/>O(log n) 看似最简单的算法"] --> B["直觉陷阱：靠'砍一半'写代码"]
A --> C["正确姿势：靠循环不变量推理"]
B --> B1["中点溢出 bug<br/>mid = (low+high)/2<br/>大数组时 low+high 超过 INT_MAX"]
B --> B2["边界 / 终止条件错<br/>low<high vs low<=high<br/>mid 还是 mid±1"]
B --> B3["Bentley 1986 实验<br/>职业程序员约 90% 写错"]
C --> C1["定义不变量<br/>答案必落在 low,high 闭区间内"]
C --> C2["每次更新推导<br/>low=mid+1 / high=mid 保持不变量"]
C --> C3["形式化验证<br/>机器证明替代测试盲区"]
B1 --> D["Java JDK 潜伏约 9 年<br/>1997→2006 Bloch 公开认错<br/>Bug 5045582"]
B1 --> E["修复写法<br/>low+(high-low)/2 或 >>> 1"]
D --> F["蔓延：C++ / .NET / 教科书 / 大模型<br/>同一个症状反复出现"]
style A fill:#fff3cd,stroke:#d39e00,stroke-width:2px
style D fill:#f8d7da,stroke:#dc3545,stroke-width:2px
style C fill:#d4edda,stroke:#28a745,stroke-width:2px
1. 给每一个写代码的人：把不变量写进注释。 下次写二分查找、写双指针、写任何带边界的循环之前，先在代码上方用一句话写下你的循环不变量（"答案一定在 [low, high] 内"），然后让每一行代码为这句话负责。你会发现，那些"< 还是 <="的纠结会自己消失，code review 时也更容易说服别人。这不是炫技，是成本最低的防 bug 手段。
2. 给测试工程师：盯数据类型，别只盯行覆盖率。 加法溢出能在 100% 行覆盖率的代码里潜伏九年，是因为没人想到去测"接近 INT_MAX 的下标"。设计边界用例时，永远要把"取值范围的极限"当作一类独立的测试目标——最大值、最小值、零、刚好越界、刚好不越界。对整数运算尤其如此。
3. 给用 AI 写代码的人：简单算法要审，复杂算法更要审。 大模型写二分查找翻车，不是因为模型不行，而是因为它在"模仿形态"而非"推理正确性"。把它当成一个快速但需要复核的初级工程师：它写的二分、排序、并发原语，你都要用不变量和边界用例去验一遍。越是"看起来显然"的代码，越值得怀疑。
4. 认知升级：警惕"简单"这个词。 Bentley 的实验、Bloch 的九年、各家标准库的连环翻车，讲的是同一个道理——"简单"不等于"容易写对"。一个算法描述越短，越容易让人放弃严谨。真正决定代码质量的，不是你能不能 5 分钟写完，而是你能不能证明它在所有输入下都对。把这种"对一切输入负责"的习惯内化，比背 100 道模板题都有用。
二分查找用九年沉默的 bug 告诉整个行业："简单"是直觉的陷阱，正确性只能靠不变量推理来担保，而测试覆盖率永远测不出数据类型里的暗礁。
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。