logo标签列表

在实际应用中二分查找算法被用在哪些地方？

algorithmbinary-search
40

每个程序员都知道二分搜索是在有序数据列表中搜索的一种好的、快速的方法。有许多玩具教科书示例使用二分搜索，但在实际编程中呢：二分搜索在哪些真实的程序中实际使用？

6
在实际应用中，什么场景下使用“将圆柱形木钉插入圆孔”的方法？ - Svante
3
我觉得在前面的答案中没有强调足够，我想澄清一个二分查找算法只适用于数据已经排序的情况。我最近举的例子就是检查一个单词是否在一个我知道已经排序的单词列表中（因为我在程序中之前自己对其进行了排序）。如果你的数据没有排序，或者不能进行排序，那么你就不能信任二分查找的结果。 - vowel-house-might
22个回答
29

二分查找（Binary search）被广泛应用在IT技术中。无论是Java、.NET、C++ STL等任何语言库中的排序集合，都会使用（或提供使用）二分查找来查找值。尽管很少需要自己实现，但仍需理解其原理以最大化利用。

24

二分查找可以在内存空间有限的情况下快速访问有序数据。假设您想要将一组100,000个32位整数存储在可搜索、有序的数据结构中，但您不经常更改该集合。您可以轻松地将整数存储在一个排序的400,000字节数组中，并且您可以使用二分查找快速访问它。但是，如果您将它们放入B树、红黑树或任何“更动态”的数据结构中，您就开始产生内存开销。例如，将整数存储在任何具有左子节点和右子节点指针的树中，将使您至少消耗1,200,000字节的内存（假设32位内存架构）。当然，您可以进行优化，但这通常是其工作原理。

由于更新有序数组（执行插入或删除）非常缓慢，因此在数组经常更改时二分查找不是很有用。

以下是我使用二分查找的一些实际示例：

  • 在虚拟机中实现“switch() ... case:”结构，其中case标签是单独的整数。如果有100个case，您可以使用二分查找在6到7步中找到正确的条目，而条件分支序列平均需要50次比较。
  • 使用后缀数组进行快速子字符串查找，后缀数组按字典顺序包含可搜索字符串集的所有后缀（我想保留内存并保持实现简单）
  • 寻找方程的数值解（当您懒得实现牛顿法时）
1
关于switch/case：除非case非常稀疏，否则编译器将建立跳转表。 - kennytm
我只是好奇你是如何实现switch case的。如果你能分享一下实现方法，那就太好了。 - Micah
16
每个程序员都需要知道如何在调试时使用二分查找。
当你有一个程序，并且知道在程序执行的特定点上存在一个错误，你可以使用二分查找来确定实际发生错误的位置。这比单步执行大量代码要快得多。
7
你能否进一步解释一下这个？我觉得我理解你的意思了，但我不同意每当发现错误时人类就在应用二分查找算法的说法。 - Polaris878
我并没有说它总是被使用，甚至也没有说它必须总是被使用。我说的是这是一项必要的技能。 - user25148
3
实际上使用二分查找的“程序”在哪里，而不是实际上在生活中使用二分查找的地方。 - nawfal
@Polaris878 虽然原始答案与现实生活中的程序无关，但 https://git-scm.com/docs/git-bisect 是一个人类应用二分查找的例子。 - talekeDskobeDa
7

二分查找是一种好的、快速的方法！

在STL和.NET框架等到来之前，您经常需要自己编写定制的集合类。每当一个排序数组可以成为存储数据的可行位置时，二分查找就是在该数组中定位条目的方式。

我相信今天二分查找仍然广泛使用，尽管由于库的便利性，它被“后台处理”了。

6
我已经在BTree实现中实现了二分搜索算法。
BTree搜索算法用于查找下一个要读取的节点块，但是在4K块本身内（其中包含基于键大小的多个键），使用二分搜索来查找记录编号（对于叶节点）或下一个块（对于非叶节点）。
与顺序搜索相比，盲目快速，因为像平衡二叉树一样，在每次检查时都会删除剩余搜索空间的一半。
4

我曾经在一个显示二维图形数据的GUI控件中实现了它（甚至不知道这实际上是二分查找）。点击鼠标应该将数据光标设置到最接近x值的点。当处理大量点（几千个，在x86只有100 MHz CPU频率的早期），这并不是真正可交互的 - 我从开始做线性搜索。经过一些思考，我意识到我可以采用分治法来解决这个问题。花了我一些时间才让它在所有边缘情况下都能正常工作。

只有一段时间后我才知道这确实是一种基本的计算机科学算法......

3
回答您的问题并举例说明。在R编程语言中，有一个名为data.table的包。它是一种基于C实现的、语法简短、性能高的数据转换扩展。它使用二进制搜索。即使没有二进制搜索，它的比竞争对手更具规模优势。
您可以在项目维基grouping 2E9中找到与python pandas和R dplyr的基准测试。
还有一个好的基准测试与数据库和大数据benchm-databases进行比较。在最近的data.table版本（1.9.6）中，二进制搜索得到了扩展，并且现在可以用作任何原子列的索引。
我刚发现了一个很好的总结，我完全同意 - see。

任何进行R比较的人都应该使用data.table而不是data.frame。特别是在基准测试方面。在我的职业生涯中，我发现data.table是最好的数据结构/查询语言。它在R世界中引领潮流，并且在所有数据重点语言中都是如此。

所以是的，二分查找正在被使用，世界因此变得更美好。

3

现在，在99%的3D游戏和应用程序中都使用二分查找。空间被划分为一棵树结构，使用二分查找来检索根据3D位置和相机要显示哪些细分。

其中最早的展示之一是《毁灭战士》。二叉树和相关搜索增强了渲染效果。

3

一个例子是stl set。其底层数据结构是平衡二叉搜索树，由于二分查找支持O(log n)的查找、插入和删除。

另一个例子是一个整数除法算法，它以对数时间运行。

两者都不是二分查找的示例。 - Antti Huima
在平衡二叉搜索树中进行查找时，会重复消除已排序集合中剩余搜索空间的一半。这就是二分查找。为了计算a/b而不使用"/"，有一个循环，它会重复将int的值加倍，直到它略微过大。同样地，我在做二分查找。 - MrDatabase
@antii.huima，嗯...是的，它们两个都是。 - Bob Somers
实际上，“二分查找”通常在已排序的数组上执行。它是一种算法。“二叉搜索树”是表示二分查找的数据结构。 - Bob Yoplait
3
我们仍然在我们的代码中广泛使用它，以每秒数千次地搜索成千上万个ACL。这很有用，因为一旦ACL从文件中进来，它们就是静态的，并且我们可以承受随着引导加入数组而导致的开销。一旦它开始运行，速度非常快。
当您可以在最多7次比较/跳跃（8个中的511个，9个中的1023个等等）中搜索255元素数组时，您可以看到二分查找是您可以得到的最快速度。
对于未接触过的人来说，什么是ACLS？我猜你不是指高级心脏生命支持。 - Stef
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接