logo标签列表

如果有三分查找，为什么要使用二分查找？

algorithmdata-structuresbinary-treeternary-tree
43

最近我听说了三分查找，它将一个数组分成三部分并进行比较。这里会有两次比较，但它可以将数组缩小到 n/3 的规模。为什么人们不经常使用它呢？

3
如果数组只有两个元素会怎样？ - Carlos Muñoz
13
这是一个特殊情况。 - mousey
1
令人惊讶的是，所有答案都只谈到时间复杂度。在许多情况下，空间复杂度同样重要，三叉树通常更具空间效率。(而且，考虑到现代CPU架构，空间复杂度经常对实际性能产生重大影响)。 - Ian Mercer
1
我很感激这个6年前的问题。你所描述的不是三分搜索，请问有人可以编辑标题吗？FYI，三分搜索适用于单峰函数，而二分搜索适用于单调函数。 - marcv81
我觉得奇怪的是没有人提到问题的假设是错误的这一事实。它并不将数组缩小到 n/3，而是缩小到三分之二，这意味着比二分搜索留下更多元素。另一方面，这两种算法的目的完全不同。三分搜索用于查找单峰函数的最小/最大值，而二分搜索算法无法完成此任务。 - Chris Vilches
15个回答
44

实际上，人们确实使用 k 叉树来处理任意的 k 值。

然而，这是一种权衡。

要在 k 叉树中查找一个元素，你需要大约 k*ln(N)/ln(k) 次操作（记住换底公式）。k 越大，总体操作次数就越多。

你所说的逻辑延伸是 "为什么不用一个 N 叉树来处理 N 个数据元素？"。当然，这将是一个数组。

4
B树是k叉树，介于数组和二叉树之间，被广泛应用；对于大于3阶的k叉树，确实有其用途。 - Dean J
9
顺便说一下，k/ln(k) 的最小值出现在 k=e（即 k=2.71），因此“最优”的 k 叉树是 e 叉树。 二叉树非常接近 e 叉树。 - Andras Nemeth
@Cucu 但是三元运算符更接近吧？ - semicolon
1
它确实更接近。但由于差异不是很大，实现的简单性变得更加重要，因此二进制胜出。 - Andras Nemeth
26

三分查找仍将给您相同的渐近复杂度O(log N)搜索时间，同时增加了实现的复杂性。

相同的论点也适用于为什么您不想要四分查找或任何其他高阶。

10
@Nikita说：Log2 N = Log3 N / Log3 2 = Constant * Log3 N = O(Log N)。在任何两个对数阶复杂度之间，始终只存在一个常数因子的差异。 - Akusete
25

对于10亿（美国十亿 - 1,000,000,000）个已排序的项目进行搜索，使用二分查找平均需要约15次比较，而三分查找则需要约9次比较 - 这并没有太大的优势。请注意，“三分比较”中每个可能包含2次实际比较。

6
“k元比较”实际上包含了“k”次关键字比较，这一事实可能是回答这个问题时需要提到的最重要因素。+1 - Alceu Costa
8
直到现在，我才知道“十亿”有不同的含义。干杯！ - Akusete
@Akusete：这儿十亿，那儿十亿……很快就会有一些大数字了。 - Michael Burr
@MichaelBurr：恐怕在一个拥有10亿条记录的数组中进行二分查找平均需要约30次比较，而不是15次;-) - chqrlie
10

哇，排名最高的答案在这方面错了，我觉得。

你的CPU不支持三进制逻辑作为单个操作；它将三进制逻辑分解成几步二进制逻辑。对于CPU来说，最优的代码是二进制逻辑。如果常见芯片支持三进制逻辑作为单个操作，那么你就是对的。

B树可以在每个节点上有多个分支；一个3阶B树是三进制逻辑。每向下一层，需要进行2次比较而不是1次，这可能会导致它在CPU时间上变慢。

然而，B树非常普遍。如果您假定树中的每个节点都将单独存储在磁盘的某个地方，那么大部分时间都将用于从磁盘读取数据... CPU不会成为瓶颈，但磁盘会成为瓶颈。因此，您采用具有100,000个子节点的B树，或者任何其他仅刚好适合一个内存块的大小。具有这种分支因子的B树很少会超过三个节点高，并且您只需要三次磁盘读取 - 三次停留在瓶颈处 - 就可以搜索巨大的数据集。

回顾：

  • 硬件不支持三进制树，因此它运行较慢。
  • B树的阶数远高于3对于大型数据集的磁盘优化很常见；一旦超过2，请选择更高于3的阶数。
4
三叉树具有三种跳转操作（如果小于则向左跳转JB，如果大于则向右跳转JA，如果相等则向下跳转JE）。二叉树具有两种跳转操作（如果小于则向左跳转JB，如果大于则向右跳转JA）。处理器是否具有二进制或三进制架构与此无关。只与IA-32架构上的指令JA、JB和JE有关。 - Abel
8
你认为三分查找算法为什么会更快呢？
平均比较次数：
in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

最坏的比较次数：

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

看起来三分搜索更糟糕。

@Moron: 是不是2 * log(n)/log3？我在一个层级里并不总是需要进行两次比较。例如，如果我有 [..a..b..]，并且 x < a 成立，那么就没有必要与 b 进行比较了。 - Lazer
@Lazer：他确实说了“最坏情况”。假设是一棵平衡树，并且查找的分布是均匀的（这是一个不太可靠的假设），你平均每个节点需要1.5次查找。 - Akusete
我不确定我们是否关注最坏情况，而是关注平均需要多长时间。 - Rusty Rob
这些数字有发布的参考资料吗？ - Xi'an ні війні
这不可能是正确的：对于二分查找，最坏情况并不是平均情况，因为只有在前几次迭代中没有找到时才会继续进行到最后一次迭代。有一半的时间，您不会到达最后一次迭代，所以肯定有问题。 - corsiKa
8
三分查找比二分查找更快的唯一方法是，如果三分区划可以以不到2倍于二分比较的代价完成。如果项目存储在排序数组中，则平均而言，三分区划将比二分区划昂贵1.66倍。然而，如果信息存储在树中，则获取信息的成本相对于实际比较的成本很高，并且缓存局部性意味着随机获取一对相关数据的成本并不比获取单个数据的成本更糟糕，因此三分或n分树可能会极大地提高效率。
5
此外，请注意，如果我们继续进行线性搜索，这个序列可以推广到线性搜索。
Binary search
Ternary search
...
...
n-ary search ≡ linear search

因此，在n元搜索中，我们将只有一个“比较”，这可能需要最多n次实际比较。
1
除了这两个极端之外，还有一些非常愉快的中间地带。看看我的答案，也许可以找到答案？ - Dean J
@Dean J：是的，你说得对。如果有内置支持，可以进行原子三元比较，那么三元搜索就是首选。但在硬件级别实现三元逻辑存在很多限制（这也是它不流行的原因之一）。我记得在某个地方读到过，e 在理论上是最经济的基数，尽管在硬件上实际执行仍然是一个问题。因此，在我们拥有支持硬件级别三元逻辑的机器之前，二进制是唯一的选择。 - Lazer
1
有趣的是，在CPU周期方面，二分查找是最优的，但如果树足够大以至于其中一部分被分页到磁盘上，那么具有巨大分支因子的n-ary树实际上效果更好。 - Dean J
2
三分搜索可以在并行架构 - FPGA和ASIC上有效地使用。例如，如果搜索所需的内部FPGA存储器少于FPGA资源的一半，您可以制作一个重复的存储器块。这将允许同时访问两个不同的存储器地址，并在单个时钟周期内进行所有比较。这是为什么100MHz FPGA有时可以胜过4GHz CPU的原因之一 :)
2
"三叉树"（ternary）搜索在最优情况下更有效，这涉及搜索第一个元素（或者也许是最后一个，具体取决于你首先进行哪种比较）。对于离末尾较远的元素，你首先要检查它们，而每次两次比较都会将数组缩小2/3，但是使用二分查找相同的两次比较会将搜索空间缩小3/4。
此外，二分查找更简单。你只需要比较并获取其中一半，而不是比较，如果小于则获取第一个三分之一，否则比较，如果小于则获取第二个三分之一，否则获取最后一个三分之一。
1
几乎所有关于二叉搜索树的教材和网站实际上都没有讨论二叉树！它们向您展示了三叉搜索树！真正的二叉树将数据存储在其叶子中，而不是内部节点（除了用于导航的键）。有些人称之为叶树，并区分于教科书中展示的节点树：
J. Nievergelt，C.-K. Wong：Binary Trees的总路径长度的上限，Journal ACM 20（1973）1-6。
以下内容来自Peter Brass的数据结构书籍。
2.1 搜索树的两种模型
在刚才给出的概述中，我们忽略了一个重要的点，起初似乎微不足道，但实际上它导致了两种不同的搜索树模型，其中任何一种都可以与以下大部分材料相结合，但其中一种更加强烈可取。
如果我们在每个节点中将查询密钥与包含在节点中的密钥进行比较，并且如果查询密钥较小，则跟随左分支，如果查询密钥较大，则跟随右分支，那么如果它们相等会发生什么？搜索树的两种模型如下：

  1. 如果查询键小于节点键，则走左分支；否则，走右分支，直到到达树的叶子节点。树内部的键仅用于比较；所有对象都在叶子节点中。

  2. 如果查询键小于节点键，则走左分支；如果查询键大于节点键，则走右分支；如果相等，则取包含在节点中的对象。

这个细节有许多后果：

{ 在模型 1 中，底层树是二叉树，而在模型 2 中，每个树节点实际上是一个三元节点，具有特殊的中间邻居。

{ 在模型 1 中，每个内部节点都有左子树和右子树（可能是树的叶节点），而在模型 2 中，我们必须允许不完整的节点，其中左或右子树可能丢失，并且仅保证存在比较对象和键。

所以，模型 1 的搜索树结构比模型 2 更加规则；至少对于实现来说，这是一个明显的优势。

在模型1中，遍历内部节点只需要进行一次比较，而在模型2中，我们需要进行两次比较来检查三种可能性。
实际上，在模型1和模型2中具有相同高度的树最多包含大约相同数量的对象，但是在模型2中需要进行两倍的比较才能到达树的最深处。当然，在模型2中也有一些对象可以更早地到达；根节点中的对象只需两次比较即可找到，但几乎所有对象都在或靠近最深层。
定理。高度为h且模型1的树最多包含2^h个对象。高度为h且模型2的树最多包含2^h+1−1个对象。
这很容易理解，因为高度为h的树具有左右子树，每个子树的高度最多为h-1，在模型2中它们之间还有一个额外的对象。
在模型1中，内部节点中的键仅用于比较，并且可能在叶子中重新出现以识别对象。在模型2中，每个键仅出现一次，与其对象一起。
在模型1中，甚至可能存在用于比较但不属于任何对象的键，例如，如果对象已被删除。通过在概念上分离这些比较和识别功能，这并不令人惊讶，在后续结构中，我们甚至可能需要定义人工测试来得到良好的搜索空间划分，而这些测试并不对应任何对象。用于比较的所有键必须是不同的，因为在模型1树中，每个内部节点都有非空的左右子树。因此，每个键最多出现两次，一次作为比较键，一次作为叶子中的识别键。
模型2成为首选的教科书版本，因为在大多数教科书中，不区分对象和其键：键就是对象。然后，在树结构中重复键变得不自然。但在所有实际应用中，键和对象之间的区别非常重要。几乎从不希望仅跟踪一组数字；这些数字通常与某些更大的信息相关联，这些信息通常比键本身大得多。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接