每个程序员都被教导二进制搜索是搜索有序数据列表的一种很好、快速的方法。有很多使用二分搜索的玩具教科书示例，但在实际编程中呢：在实际程序中实际使用二分搜索在哪里？
tjdonaldson
问问题
43336 次
22 回答
27
二进制搜索无处不在。从任何语言库（Java、.NET、C++ STL 等）中获取任何排序的集合，它们都将使用（或可以选择使用）二进制搜索来查找值。虽然您必须很少实施它，但您仍然必须了解它背后的原理才能利用它。
于 2009-02-12T07:35:04.953 回答
23
当内存空间紧张时，可以使用二分查找快速访问有序数据。假设您想将一组 100.000 个 32 位整数存储在一个可搜索的有序数据结构中，但您不会经常更改该集合。您可以轻松地将整数存储在 400.000 字节的排序数组中，并且可以使用二进制搜索快速访问它。但是，如果您将它们放入例如 B-tree、RB-tree 或任何“更动态”的数据结构中，您就会开始产生内存开销。为了说明，将整数存储在具有左子和右子指针的任何类型的树中都会使您消耗至少 1.200.000 字节的内存（假设 32 位内存架构）。当然，您可以进行一些优化，但一般情况下就是这样。
因为更新有序数组（进行插入或删除）非常慢，所以当数组经常变化时，二分查找就没有用了。
这里有一些我使用二进制搜索的实际示例：
- 在案例标签是单个整数的虚拟机中实现“switch() ... case:”构造。如果您有 100 个案例，您可以使用二分搜索在 6 到 7 个步骤中找到正确的条目，其中条件分支序列平均需要进行 50 次比较。
- 使用后缀数组进行快速子字符串查找，其中包含按字典顺序排列的可搜索字符串集的所有后缀（我想节省内存并保持实现简单）
- 寻找方程的数值解（当你懒惰并且不介意实现牛顿法时）
于 2009-02-12T17:47:27.027 回答
15
每个程序员在调试时都需要知道如何使用二进制搜索。
如果您有一个程序，并且您知道在程序执行期间的某个特定点处可见错误，则可以使用二进制搜索来确定错误实际发生的位置。这比单步执行大部分代码要快得多。
于 2009-02-12T07:31:34.480 回答
7
二分查找是一种又好又快的方法！
在 STL 和 .NET 框架等到来之前，您经常会遇到需要滚动自己的自定义集合类的情况。每当排序数组成为存储数据的可行位置时，二进制搜索就是在该数组中定位条目的方式。
我很确定二进制搜索在今天也被广泛使用，尽管为了您的方便，它由库“在后台”处理。
于 2009-02-12T05:38:23.703 回答
6
我已经在 BTree 实现中实现了二进制搜索。
BTree 搜索算法用于查找要读取的下一个节点块，但在 4K 块本身（包含基于密钥大小的多个密钥）中，二进制搜索用于查找记录号（对于叶节点) 或下一个块（对于非叶节点）。
与顺序搜索相比，速度快得惊人，因为就像平衡二叉树一样，每次检查都会删除一半的剩余搜索空间。
于 2009-02-12T05:48:24.350 回答
4
我曾经为一个在图形中显示二维数据的 GUI 控件实现了它（甚至不知道这确实是二进制搜索）。用鼠标单击应将数据光标设置到具有最接近 x 值的点。当处理大量点时（几个 1000，这是 x86 刚刚开始超过 100 MHz CPU 频率的时候），这并不是真正可用的交互式 - 我从一开始就进行线性搜索。经过一番思考，我突然想到我可以分而治之的方式来解决这个问题。我花了一些时间让它在所有边缘情况下工作。
过了一段时间我才知道这确实是一个基本的 CS 算法……
于 2009-02-12T07:42:30.473 回答
3
一个例子是 stl 集。底层数据结构是一个平衡的二叉搜索树，由于二叉搜索，它支持 O(log n) 中的查找、插入和删除。
另一个例子是在对数时间内运行的整数除法算法。
于 2009-02-12T05:37:33.490 回答
3
我们仍然在代码中大量使用它来每秒搜索数千次数千次 ACLS。这很有用，因为 ACL 一旦从文件中进入，它们就是静态的，而且我们可能会因为在启动时添加阵列而承受增长阵列的代价。一旦它运行也非常快。
当您最多可以在 7 次比较/跳转中搜索 255 个元素的数组时（8 次中的 511 次，9 次中的 1023 次等），您可以看到二进制搜索的速度几乎与您所能获得的一样快。
于 2009-02-12T06:02:16.953 回答
3
通过动手示例回答您的问题。
在 R 编程语言中有一个包data.table。它从 C 实现的、短语法、高性能的数据转换扩展中得知。它使用二进制搜索。即使没有二分搜索，它的扩展性也比竞争对手好。您可以在项目 wiki分组 2E9 - 随机顺序数据
中找到基准 vs python pandas和 vs R dplyr 。
还有很好的 benchmark vs databases vs bigdata benchm-databases。
在最近的 data.table 版本 (1.9.6) 中，二进制搜索得到了扩展，现在可以用作任何原子列的索引。
我刚刚找到了一个很好的总结，我完全同意 -见。
任何进行 R 比较的人都应该使用 data.table 而不是 data.frame。基准测试更是如此。data.table 是我职业生涯中发现的最好的数据结构/查询语言。它在 R 世界中处于领先地位，以我的方式，在所有以数据为中心的语言中都处于领先地位。
所以是的，二进制搜索正在被使用，并且由于它，世界变得更好了。
于 2015-10-31T21:39:20.930 回答
2
好吧，现在 99% 的 3D 游戏和应用程序都使用了二分搜索。空间被划分为树结构，并使用二分搜索根据 3D 位置和相机检索要显示的细分。
它的第一个最伟大的展示之一是 Doom。二叉树和相关的搜索增强了渲染。
于 2010-03-04T14:42:13.587 回答
2
二进制搜索可用于使用 Git 进行调试。它被称为git bisect。
于 2014-03-02T09:35:25.157 回答
1
Binary sort is useful in adjusting fonts to size of text with constant dimension of textbox
于 2012-04-08T09:05:14.930 回答
1
在其他地方，我有一个解释器，其中有一个命令名称表和一个指向解释该命令的函数的指针。大约有 60 个命令。使用线性搜索不会非常繁重 - 但我使用二进制搜索。
于 2009-02-12T06:03:12.303 回答
1
用于测量数字时序或模拟电平的半导体测试程序广泛使用二进制搜索。来自 Advantest、Teradyne、Verigy 等的自动测试设备 (ATE) 可以被认为是真值表爆破器，应用输入逻辑并验证数字部件的输出状态。
考虑一个简单的门，输入逻辑在每个周期的时间 = 0 处发生变化，并在输入逻辑发生变化后转换 X ns。如果在 T=X 之前选通输出，则逻辑与预期值不匹配。选通晚于时间 T=X，并且逻辑与预期值匹配。二进制搜索用于查找逻辑不匹配的最新值与它匹配的最早部分之间的阈值。（Teradyne FLEX 系统将时序解析为 39pS 分辨率，其他测试仪具有可比性）。这是一种测量过渡时间的简单方法。相同的技术可用于求解建立时间、保持时间、可操作电源电平、电源与延迟等。
任何类型的微处理器、存储器、FPGA、逻辑和许多模拟混合信号电路都在测试和表征中使用二进制搜索。
——迈克
于 2009-02-12T07:51:08.737 回答
1
于 2010-03-04T15:59:29.573 回答
1
我有一个程序迭代一个集合来执行一些计算。我认为这是低效的，所以我对集合进行了排序，然后使用单个二进制搜索来查找感兴趣的项目。我退回了这个项目及其匹配的邻居。我实际上过滤了集合。
这样做实际上比迭代整个集合和找出匹配项要慢。
我继续向集合中添加项目，因为我知道排序和搜索性能最终会赶上迭代。它收集了大约 600 个对象，直到速度相同。1000 个对象具有明显的性能优势。
我还会考虑您正在使用的数据类型、重复和传播。这将对排序和搜索产生影响。
我的答案是尝试这两种方法并为它们计时。
于 2009-08-07T15:10:16.683 回答
0
Python的list.sort()方法使用Timsort（AFAIK）使用二分搜索来定位元素的位置。
于 2010-02-14T21:00:39.933 回答
0
寻找方程的根可能是您想要使用二进制搜索等非常简单的算法做的那些非常简单的事情之一。
于 2009-02-16T06:20:44.120 回答
0
Delphi 使用在排序的 TStringList 中搜索字符串时可以享受二分查找。
于 2009-05-06T07:34:14.800 回答
0
我相信 .NETSortedDictionary在幕后使用二叉树（很像 STL 映射）......所以使用二叉搜索来访问SortedDictionary
于 2009-08-07T15:15:58.437 回答
0
二分搜索提供了许多现成的地图/字典实现所没有的功能：查找非精确匹配。
例如，我使用二分搜索来实现基于 GPS 日志的照片地理标记：将所有 GPS 航点放在一个按时间戳排序的数组中，并使用二分搜索来识别在时间上最接近每张照片时间戳的航点。
于 2010-03-04T14:54:10.743 回答
-1
如果要在数组中查找一组元素，则可以线性搜索每个元素，也可以对数组进行排序，然后使用具有相同比较谓词的二进制搜索。后者要快得多。
于 2009-02-12T05:39:08.180 回答