Engineering Handbook 二分查找教程：从标准模板到旋转数组，告别 off-by-one 错误

Engineering Handbook（engineering-handbook） 是一套开源的 DSA（数据结构与算法）与系统设计手册，其中「搜索与排序」章节专门讲解了二分查找：标准模板、旋转数组变体，以及如何彻底告别 off-by-one（差一）错误。本教程带你快速上手二分查找模板，从闭区间精确匹配写到旋转数组分支判断，一次写对、不再踩坑。

🎯 适合人群：准备算法面试的新手、写对 while lo <= hi 却总错在边界上的同学

一、为什么二分查找是最经典的"翻车现场"？

二分查找逻辑简单，却是 bug 的重灾区。最著名的事故来自 2006 年：Google 的 Joshua Bloch 发文指出 java.util.Arrays.binarySearch 里的中点计算 low + high 在超大数组上会整数溢出，而这段错误代码已经在标准库里躺了 9 年。

问题就一行：

mid = (lo + hi) // 2      # ❌ 可能溢出
mid = lo + (hi - lo) // 2 # ✅ 安全写法，任何语言都建议用这个

而比溢出更常见的，是 off-by-one 错误：lo <= hi 还是 lo < hi、hi = mid 还是 hi = mid - 1，这些细节决定了你的循环会不会死循环、会不会漏掉边界元素。

Handbook 给出的核心心法只有一句话：

先写下"循环不变量"，再写代码。 模板只是不变量的产物。

二、模板选择指南：按"问题形态"选模板

同样是"排好序的数组 + 一个目标值"，三种问法对应三套不同模板，用错就会引入 off-by-one bug：

问题形态	典型题目	模板	区间风格	循环条件	没找到时
是否存在？返回下标	LC 704	模板 A（精确匹配）	闭区间 [lo, hi]	lo <= hi	返回 -1
应该插到哪个位置？	LC 35	模板 B（下界 lower_bound）	半开区间 [lo, hi)	lo < hi	返回插入点 lo
最小的满足条件的 i？	LC 278	模板 C（谓词驱动）	半开区间 [lo, hi)	lo < hi	保证存在

💡 口诀：闭区间配 <=，半开区间配 <；区间风格定了，指针更新和返回值就都定了一半。

模板 A：精确匹配（闭区间）

最常用的一套，记住不变量："如果 target 存在，它的下标一定在 [lo, hi] 里"：

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

关键点：mid 已经被比过并排除了，所以两个指针都要越过 mid（mid + 1 / mid - 1）。写成 lo = mid 或 hi = mid 就是最常见的死循环来源。

模板 B：下界与插入位置（半开区间）

问法换成"target 该插在哪"时，hi 从数组末尾外一格（len(nums)）开始，循环退出时 lo == hi 就是答案。这个形态和 C++ 的 std::lower_bound、Python 的 bisect_left 完全一致。

📌 变体只需改一个比较符：nums<a href="https://link.gitcode.com/i/d2de1102c8b68c66ea26bc983b76e1d1" target="_blank">mid] < target（下界）与 nums[mid] <= target（上界），其余代码逐字节相同。详见 [content/dsa/part-2-search-sort/02-binary-search-variants.md

三、快速上手：获取 Handbook 手册

如果想阅读完整章节原文（含逐步演算表格和四语言对照解法），可以克隆仓库离线学习：

git clone https://gitcode.com/gh_mirrors/engin/engineering-handbook

与本教程直接相关的章节与文件：

资料	路径	说明
标准模板章节	content/dsa/part-2-search-sort/01-binary-search-canonical.md	A/B/C 三模板 + off-by-one 详解
变体章节（旋转数组等）	content/dsa/part-2-search-sort/02-binary-search-variants.md	旋转数组、峰查找、对答案二分
Python 解法	content/dsa/part-2-search-sort/01-binary-search-canonical/sol.py#L12-L27	三套模板完整实现
Java / C++ / Go 对照解法	sol.java、sol.cpp、sol.go	同一模板的四种语言写法
前置：线性查找	content/dsa/part-2-search-sort/00-linear-search.md	二分查找的铺垫章节
交互式演示规格	content/dsa/widgets/w-04-binary-search.yml	二分查找动画（精确匹配 + 旋转）

四、告别 off-by-one：3 步自查清单

Handbook 把高频 bug 总结成了 3 条铁律，写完代码逐条过一遍：

1. 中点永远用 lo + (hi - lo) // 2，杜绝溢出（LC 278 的 n 上限就是 INT_MAX，专治这个 bug）。
2. 循环条件由区间风格决定：闭区间 [lo, hi] 用 lo <= hi（单元素区间还要探一次）；半开区间 [lo, hi) 用 lo < hi（lo == hi 就是终止态）。
3. 返回值必须从不变量推导：模板 A 返回 -1，模板 B/C 返回 lo。直接"背返回值"会在变体题上翻车。

典型错误	症状	正确写法
(lo + hi) // 2	大数组溢出、越界	lo + (hi - lo) // 2
闭区间写 while lo < hi	单元素/首尾元素漏查	while lo <= hi
闭区间写 hi = mid	两元素时死循环	hi = mid - 1
半开区间写 hi = mid - 1	丢掉合法候选、答案错位	hi = mid

五、旋转数组：模板 A + 一个分支

面试进阶题 LC 33「搜索旋转排序数组」的输入形如 [4, 5, 6, 7, 0, 1, 2]——整体无序，但 mid 的左半边或右半边必有一侧是有序的。做法是每轮多一次比较，先定位有序的那半边，再看 target 是否落在它的值域内：

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # 左半边有序（注意必须是非严格 <=）
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                      # 右半边有序
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

两个易错点：

• ✅ 分支判断必须用非严格 nums[lo] <= nums[mid]，否则两元素数组 [3, 1] 会判错方向；
• ✅ 求旋转数组最小值（LC 153）时，要拿 nums[mid] 和右端点 nums[hi] 比，而不是 nums[lo]。

完整逐行演算（每步 lo / hi / mid 的变化表）见 content/dsa/part-2-search-sort/02-binary-search-variants.md#L255-L266。

六、练习路线：从 Easy 到 Hard 的爬梯

按照 Handbook 的"问题阶梯"安排练习顺序，难度递进、模式复用：

阶段	题目	练的模板	难度
🟢 入门	LC 704 二分查找	模板 A	Easy
🟢 入门	LC 35 搜索插入位置	模板 B	Easy
🟢 入门	LC 278 第一个错误的版本	模板 C	Easy
🟡 进阶	LC 33 搜索旋转排序数组	模板 A + 分支	Medium
🟡 进阶	LC 153 旋转数组的最小数字	旋转枢轴	Medium
🟡 进阶	LC 162 寻找峰值	斜率谓词	Medium
🔴 挑战	LC 4 两个有序数组的中位数	跨数组分界	Hard

七、小结

• 先不变量，后代码：写下"答案一定在哪个区间"，模板自然浮现，off-by-one 无处可藏。
• 闭区间 <=，半开区间 <，中点用 lo + (hi - lo) // 2，这三条是肌肉记忆。
• 旋转数组 = 模板 A + 一次分支，掌握后 LC 153 / LC 162 都是同源变形。

学有余力的读者可以继续沿着 content/dsa/part-2-search-sort/ 目录进入比较排序与快速选择章节，二分查找的"对答案二分"思想还会在动态规划部分再次登场。