二分查找 - 每次消灭一半可能性
057二分搜索：对半分的艺术
📰 5W1H 发明者故事
Who（何人）- 发明者是谁？
发明者：约翰·莫奇利（John Mauchly，ENIAC发明者之一，1946年提出）；计算机科学界通常将其正式描述归功于多人
背景：莫奇利（1907-1980）是ENIAC的联合发明者，美国物理学家和计算机先驱。二分查找的思想更古老——图书馆员翻字典时就用"折中"法——但莫奇利在1946年的讲座中首次将其形式化为计算机算法。然而，第一个正确的无bug二分查找程序，直到1962年才由德里克·莱默（Derrick Henry Lehmer）写出。克努斯指出：大多数程序员写的二分查找都有整数溢出的bug（直到2006年才被谷歌工程师发现）。
当时的处境：1946年，ENIAC刚刚建成。如何在大量数据中快速找到目标，是早期计算机最实际的需求之一。电话簿、词典、银行账户——如何用最少的比较次数找到目标？
When（何时）- 什么时候发明的？
时间：1946年（莫奇利讲座）；1960年代（第一个无bug实现）
时代背景：
- 1946年：ENIAC问世，计算机时代开始
- 1952年：IBM701商业电脑，大规模数据处理需求出现
- 克努斯1973年出版TAOCP第三卷，对二分查找进行了详细分析
- 2006年：谷歌工程师约书亚·布洛克（Joshua Bloch）撰文指出Java标准库二分查找的整数溢出bug（mid = (low+high)/2 在large indices时溢出）
Where（何地）- 在哪里发明的？
地点：宾夕法尼亚大学（ENIAC所在地），后来在贝尔实验室进一步完善
环境：二战后的美国，大量军事和商业数据处理需求推动了搜索算法的研究。
What（何事）- 发明了什么？
算法：二分查找（Binary Search）
核心思想：在有序数组中，每次检查中间元素。如果目标等于中间元素则找到；如果目标更小，则在左半段继续；如果更大，则在右半段继续。每次比较消灭一半的搜索空间。
时间复杂度：O(log n)——n=10亿时，最多只需约30次比较。
著名bug：
intmid=(low+high)/2;/* 当 low+high > INT_MAX 时溢出！ */intmid=low+(high-low)/2;/* 正确写法 */Why（何因）- 为什么发明？
问题：顺序查找（从头到尾）是O(n)。对于10亿条记录，每次查找要检查平均5亿条——不可接受。
洞察：如果数据有序，每次比较可以排除一半的元素，最多 log₂(n) 次即可找到答案。
现实动力：电话本、数据库、字典索引——都是有序的，都需要快速查找。
How（何果）- 如何实现？有什么影响？
历史影响：
- 数据库索引（B树）是二分查找的推广，支持动态插入
- 编译器的符号表查找
- 操作系统的内存页表查找
- 克努斯在TAOCP中专门讨论了"二分查找的正确实现"，警告了常见错误
- lower_bound / upper_bound（C++ STL）是二分查找的扩展
📝 自然语言需求定义
需求名称：实现二分查找，包含迭代版、递归版、lower_bound和upper_bound
功能需求
- 迭代二分查找：在有序数组中找target，返回下标或-1
- 递归二分查找：同上，用递归实现
- lower_bound：返回第一个 ≥ target 的下标
- upper_bound：返回第一个 > target 的下标（即target范围的右边界）
- count_occurrences：统计target在有序数组中出现次数
验收标准
| 编号 | 测试场景 | 预期结果 | 验证方式 |
|---|---|---|---|
| 1 | 查找存在的元素（11）在[1,3,…,19] | 下标5 | 直接验证 |
| 2 | 查找第一个元素（1） | 下标0 | 直接验证 |
| 3 | 查找最后一个元素（19） | 下标9 | 直接验证 |
| 4 | 查找不存在的元素（6） | -1 | 直接验证 |
| 5 | 递归与迭代结果一致 | 所有元素一致 | 批量对比 |
| 6 | lower_bound/upper_bound in [1,2,2,2,3] | lb=1, ub=4, count=3 | 直接验证 |
| 7 | 单元素数组 | 找到返回0，找不到返回-1 | 边界条件 |
💻 C语言实现文件
对应文件:binary_search.c
编译运行:
gcc-obinary_search_test binary_search.c ./binary_search_test
