很少有算法能像二分查找这样回报清晰的思考：寥寥数行代码，就能把 O(n) 的扫描变成 O(log n) 的查找，把解法从可怕的“超出时间限制”判定中拯救出来。
如果你的孩子正向着像 USA Computing Olympiad 这样的竞赛攀登，二分查找是首批值得掌握的技巧之一。它出现得极其频繁，实现起来很快，还能培养强手随处依赖的一种习惯：发现问题中的结构并加以利用。在 BIAA，我们把它视为竞赛编程路线中的一项基础工具。
核心思想：在有序、单调的空间中查找
经典的二分查找是在有序数组中寻找某个值。你维护一个下界和上界，查看中间元素，并舍弃不可能包含目标的那一半。每一步都把搜索空间减半，因此在一百万个元素中找到答案只需大约二十次比较。
使顶尖选手脱颖而出的更深层洞见在于：二分查找其实并不真正需要数组。它适用于任何单调谓词——一个是/否的问题，其答案在你沿着有序范围移动时恰好翻转一次。如果某个候选值可行，那么它一侧的所有值也都可行；如果它不可行，那么另一侧的所有值也都不可行。这唯一的一次翻转，正是二分查找所追寻的边界。
每当一个问题要求找出可行的最小值，或仍然能满足的最大值时，就问问可行性是否单调。如果是，二分查找通常就是出路。
对答案进行二分
这是赢下最多竞赛题目的模式，然而初学者却很少能识别出它。你不是在数据中查找，而是在可能的答案中查找。
假设一道题要求找出使配送能在截止时间内完成所需的最小运力。直接计算这个运力可能很难。但检验单个猜测——“运力为 X 时，我们能否按时完成？”——往往通过贪心扫描或快速模拟就很容易做到。而且可行性是单调的：如果运力 X 可行，任何更大的运力也可行。于是你在可能的运力范围上做二分查找，并在每个中点处运行你的可行性检验。
这套套路很可靠：
- 确定数值答案空间（可以是整数或实数）。
- 编写一个返回真或假的
check(x)函数，要快到足以反复调用。 - 确认
check在该空间上是单调的。 - 二分查找答案发生变化的那个边界。
这种“先猜测，再验证”的分解方式，在奥林匹克数学中同样出现，在那里，给答案定界并证明其可行性是一种标准策略。
先用库，再学 bug
在 C++ 中，标准模板库已经提供了久经考验的辅助函数。lower_bound 返回第一个大于或等于目标值的元素位置；upper_bound 返回第一个严格大于目标值的位置；而 binary_search 只是报告是否存在。优先使用这些函数可以避免许多自找的错误，在竞赛压力下也写得更快。
当你必须手写循环时——做对答案的二分时你就得手写——三类 bug 导致了大多数隐藏测试失败：
- 中点处的溢出。写成
mid = (low + high) / 2可能使定长整数溢出。这在 Java 的标准库中曾是一个真实存在的缺陷，多年未被发现，直到 2006 年才修复。请优先使用mid = low + (high - low) / 2。 - 死循环。不一致地更新边界——例如在不变式期望
mid - 1时却设置high = mid——可能使循环永远停滞。 - 差一错误。混淆
while (low < high)和while (low <= high)可能悄无声息地跳过第一个或最后一个元素。
如何练习
从普通的有序数组查找开始，然后进阶到“最小化最大值”和“最大化最小值”的题目，这些几乎总是伪装起来的对答案二分。先做几道，然后回看你最快出错的提交，找出你遗漏的边界模式。在认真尝试之后再阅读题解，比直接冷读题解更能培养这种识别能力。
请注意，各项竞赛的赛制、组别和参赛资格各不相同，且会随时间变化，因此在报名前请务必在每项竞赛的官方网站上确认最新详情。
准备好把模式识别转化为排名成绩了吗？探索 BIAA 的竞赛编程课程，通过结构化的练习与导师指导来构建这些技能。