二分查找 - 每次消灭一半可能性057二分搜索对半分的艺术 5W1H 发明者故事Who何人- 发明者是谁发明者约翰·莫奇利John MauchlyENIAC发明者之一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标准库二分查找的整数溢出bugmid (lowhigh)/2 在large indices时溢出Where何地- 在哪里发明的地点宾夕法尼亚大学ENIAC所在地后来在贝尔实验室进一步完善环境二战后的美国大量军事和商业数据处理需求推动了搜索算法的研究。What何事- 发明了什么算法二分查找Binary Search核心思想在有序数组中每次检查中间元素。如果目标等于中间元素则找到如果目标更小则在左半段继续如果更大则在右半段继续。每次比较消灭一半的搜索空间。时间复杂度O(log n)——n10亿时最多只需约30次比较。著名bugintmid(lowhigh)/2;/* 当 lowhigh INT_MAX 时溢出 */intmidlow(high-low)/2;/* 正确写法 */Why何因- 为什么发明问题顺序查找从头到尾是O(n)。对于10亿条记录每次查找要检查平均5亿条——不可接受。洞察如果数据有序每次比较可以排除一半的元素最多 log₂(n) 次即可找到答案。现实动力电话本、数据库、字典索引——都是有序的都需要快速查找。How何果- 如何实现有什么影响历史影响数据库索引B树是二分查找的推广支持动态插入编译器的符号表查找操作系统的内存页表查找克努斯在TAOCP中专门讨论了二分查找的正确实现警告了常见错误lower_bound / upper_boundC 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递归与迭代结果一致所有元素一致批量对比6lower_bound/upper_bound in [1,2,2,2,3]lb1, ub4, count3直接验证7单元素数组找到返回0找不到返回-1边界条件 C语言实现文件对应文件:binary_search.c编译运行:gcc-obinary_search_test binary_search.c ./binary_search_test
