基本思路
在有序列表中,一次比较告诉你的不只是是否找到了目标,还告诉你目标在哪一边。把目标与中间的值比较。相等就完成了。如果中间值较小,它前面的所有值也都较小,所以目标只可能在它之后。如果较大,目标只可能在它之前。只保留那一半,然后重复。
一个例子
在 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 中查找 23。中间值是 16,较小,所以只剩 23 到 91。它们的中间值是 56,较大,所以只剩 23 和 38。它们的中间值是 23:经过 3 次比较在第 6 位找到,而线性搜索需要 6 次。在同一列表中查找 40,会依次比较 16、56、23 和 38,之后什么都不剩:4 次比较就知道 40 不在列表中,线性搜索则需要 10 次。
减半很快见效
一次比较后最多剩下一半,两次后剩四分之一,k 次后最多约 n/2ᵏ。查找在什么都不剩时停止,所以最多需要 ⌊log₂ n⌋ + 1 次比较:40 个值需要 6 次,1000 个需要 10 次,一百万个需要 20 次,十亿个需要 30 次。列表长度翻倍,只多一次比较。这记作 O(log n)。
说来容易,写对很难
John Mauchly 在 1946 年描述了二分查找,但据 Donald Knuth 所说,对任意列表长度都正确的第一个版本直到 1962 年才发表。Jon Bentley 后来发现,只有大约十分之一的专业程序员能写对:结束条件以及切分时的加一减一很容易出错。2006 年,Joshua Bloch 指出,求中间位置的常见写法 (low + high) / 2 在列表很长时可能溢出,这个 bug 在 Java 库中存在了多年。像本应用这样写成 low + (high − low) / 2 就能避免。
变体与应用
有重复值时,二分查找会找到其中一个匹配项;继续向左或向右查找的版本可以找到第一个或最后一个,或者缺失值应插入的位置。同样的减半思路可以求方程的根(二分法),找出 bug 最早出现的版本(git bisect),也能解决许多最优化问题。二叉搜索树存储数据的方式,让每次查找都沿着同样的减半路径进行。
动手试试
打开应用,在“查找”中选择一个值,然后按“单步”。阴影部分是目标仍可能所在的范围;中间值会高亮,被排除的一半会变淡。卡片显示还有多少个值仍有可能,以及线性搜索查找同一个值需要多少次比较。查找一个不存在的值,或使用 40 根柱子,看差距如何拉大。
常见问题
二分查找的时间复杂度是多少?
O(log n):n 个值最多 ⌊log₂ n⌋ + 1 次比较。最好情况是目标正好在中间,只需一次比较。迭代版本只需 O(1) 的额外内存。
二分查找和线性搜索有什么区别?
线性搜索依次检查每个值,适用于任何列表,但可能需要 n 次比较。二分查找只适用于有序列表,但每次比较都能排除剩余部分的一半,所以只需约 log₂ n 次。
为了用二分查找而先排序值得吗?
只有要多次查找时才值得。排序大约需要 n log n 步,比一次线性搜索还多。列表排好后,之后的每次查找都非常省事。
二分查找能用于列表以外的东西吗?
可以,只要有一种测试能告诉你在答案的哪一边:一个数值范围、一个程序的各个版本,或者猜大小游戏中的猜测。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
试试二分查找