为什么使用二进制search，如果有三元search？

我最近听说三元search，我们把一个数组分成3个部分进行比较。这里会有两个比较，但它将数组减less到n / 3。为什么人们不用这么多？

实际上，人们使用k-ary树的任意k。

但是，这是一个折衷。

要find一个k进化树中的元素，需要在k * ln（N）/ ln（k）运算（记住基变换公式）。你的k越大，你需要的整体操作就越多。

你所说的逻辑扩展是“为什么人们不使用N元树来处理N个数据元素？”。当然，这将是一个数组。

三元search仍然会给你相同的渐近复杂度O（log N）search时间，并增加实现的复杂性。

可以这样说，为什么你不想要一个四search或任何其他更高的顺序。

search10亿（10亿至10亿美元）的sorting项目将平均约15比较二进制search和约9比较与三元search – 不是一个巨大的优势。并注意每个“三元比较”可能涉及2个实际比较。

哇。我认为，最高票的答案错过了这一艘船。

您的CPU不支持三态逻辑作为一个单一的操作; 它把三进制逻辑分解成二进制逻辑的几个步骤。 CPU的最佳代码是二进制逻辑。如果筹码普遍支持三元逻辑作为一个单一的操作，你会是对的。

B-树在每个节点可以有多个分支; 一个3阶B树是三元逻辑。树中的每一步都会进行两次比较而不是一次，这可能会导致CPU时间变慢。

但是B-Trees很常见。如果你假定树中的每个节点都将被存储在磁盘上的某个地方，那么你将花费大部分的时间从磁盘读取数据……而CPU不会成为瓶颈，但磁盘将会是。所以你每个节点拿一个有10万个孩子的B树，或者其他什么东西几乎不能放进一块记忆里。具有这种分支因子的B树很less会超过三个节点高，而且只有三个磁盘读取 – 三个瓶颈 – 才能search一个庞大而庞大的数据集。

回顾：

三元树不受硬件支持，所以运行速度较慢。
对于大数据集的磁盘优化来说，订单数量远远高于3的B订单是常见的; 一旦你超过2，超过3。

三元search比二元search更快的唯一方法是如果三路分区确定可以以低于双向比较的成本的大约1.55倍来完成。如果项目被存储在一个sorting的数组中，那么三维测定的平均成本是双向测定的1.66倍。然而，如果将信息存储在树中，则获取信息的成本相对于实际比较的成本较高，并且caching位置意味着随机获取一对相关数据的成本并不比获取单个基准，三元或n元树可以大大提高效率。

是什么让你觉得三元search应该更快？

平均比较次数：

 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).

所以看起来三元search更糟。

此外，请注意，如果我们继续，这个序列推广到线性search

 Binary search Ternary search ... ... n-ary search ≡ linear search

那么，在一个n-arysearch中，我们将会有“唯一的比较”，这可能会导致n个实际的比较。

在最好的情况下，“Terinary”（三元？）search更有效率，这将涉及search第一个元素（或者最后一个，取决于您首先进行的比较）。对于距离结尾较远的元素，首先要检查，而两次比较会使arrays每次缩小2/3，与二分search相同的两个比较会缩小search空间3/4。

除此之外，二分查找更简单。你只是比较，得到一半或另一半，而不是比较，如果less于前三分之一，否则比较，如果less于三分之二，否则得到最后三分之一。

三元search可以有效地用于并行架构 – FPGA和ASIC。例如，如果search所需的内部FPGA内存less于FPGA资源的一半，则可以制作一个重复的内存块。这将允许同时访问两个不同的存储器地址，并在一个时钟周期内进行所有比较。这就是为什么100MHz的FPGA有时会超越4GHz CPU的原因之一:)

这里有一些随机的实validation据，我根本没有审查，显示它比二分查找慢。

几乎所有的二叉search树的教科书和网站都没有真正谈论二叉树！他们向你展示三元search树！真正的二叉树将数据存储在树叶中，而不是内部节点（除了导航键）。有些人称这些叶子为树，并在教科书中显示节点树：

J. Nievergelt，C.-K. Wong：二叉树总path长度的上限，Journal ACM 20（1973）1-6。

以下关于这个是Peter Brass关于数据结构的书。

2.1search树的两种模型

在刚刚提到的纲要中，我们强调了一个重要的观点：起初似乎是微不足道的，但实际上它导致了两种不同的search树模型，其中任何一种都可以与以下大部分材料结合使用，但是其中之一是强烈优先的。

如果我们在每个节点中将查询关键字与包含在节点中的关键字进行比较，并且在查询关键字较小的情况下跟随左分支，如果查询关键字较大则跟随右分支，那么如果它们相等，会发生什么？ search树的两种模型如下：

如果查询关键字小于节点关键字，则取左边的分支; 否则取右分支，直到到达树的一片叶子。树的内部节点中的密钥仅用于比较; 所有的物体都在叶子里。
如果查询关键字小于节点关键字，则取左边的分支; 如果查询关键字大于节点关键字，则select右边的分支; 如果它们相等，则将节点中包含的对象取出。

这个小问题有一些后果：

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

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

因此，模型1的search树的结构比模型2的树的结构更规整; 这至less对于实施来说是一个明显的优势。

{在模型1中，遍历一个内部节点只需要一个比较，而在模型2中，我们需要两个比较来检查三种可能性。

事实上，模型1和模型2中高度相同的树木至多包含大约相同数量的物体，但在模型2中需要两倍的比较才能达到树木的最深处。当然，在模型2中，也有一些早已到达的对象。 find根中的对象只有两个比较，但是几乎所有的对象都处于或接近最深的水平。

定理。高度h和模型1的树最多包含2 ^ h个对象。高度h和模型2的树最多包含2 ^ h + 1 – 1个对象。

这很容易看出来，因为高度为h的树的左右子树的高度至多为h – 1，在模型2中它们之间还有一个额外的对象。

{在模型1中，内部节点中的键仅用于比较，并可以重新出现在树叶中以识别对象。在模型2中，每个键与其对象一起只出现一次。

在模型1中甚至有可能存在不属于任何对象的用于比较的键，例如，如果该对象已被删除。通过在概念上将这些比较和识别function分开，这并不令人惊讶，在后来的结构中，我们甚至可能需要定义与任何对象不相对应的人为testing，以便对search空间进行良好的划分。用于比较的所有密钥必然是不同的，因为在模型1树中，每个内部节点具有非空的左和右子树。所以每个键最多出现两次，一次作为比较键，一次作为叶中的标识键。

模型2成为首选的教科书版本，因为在大多数教科书中，对象与其关键之间的区别并不是：关键是对象。那么在树结构中复制密钥就变得不自然了。但在所有的实际应用中，关键和对象之间的区别是非常重要的。一个人几乎不希望跟踪一组数字; 这些数字通常与一些更多的信息相关联，这些信息往往比密钥本身大得多。

你可能已经听说过三元search被用在涉及衡量标尺的谜语中。这些量表可以返回3个答案：左面更轻，两面相同，或左面更重。所以在三元search中，只需要1比较。但是，计算机使用布尔逻辑，只有2个答案。要进行三元search，实际上你必须进行2次比较，而不是1次。我想有些情况下，前面提到的海报可能会更快，但是你可以看到三元search并不总是更好，在计算机上执行更混乱和不自然。

理论上讲，在e上达到了k/ln(k)的最小值，而且由于3比e更接近于2，所以需要较less的比较。你可以检查3/ln(3) = 2.73..和2/ln(2) = 2.88..二进制search可能更快的原因是它的代码将有更less的分支，并且在现代CPU上运行得更快。

我刚刚发布了关于三元search的博客，我已经展示了一些结果。我也提供了一些关于我的git repo的初始级别的实现，我完全同意每一个关于三元search的理论部分，但为什么不试一试呢？如果你有三年的编码经验，那么按照这个部分就足够简单了。我发现，如果你有大量的数据集，你需要多次search三元search有一个优势。如果你认为你可以做更好的三元search去。

尽pipe在两个search树中都有相同的大O复杂度（ln n），但差异在于常量。你必须做更多的比较三级search树在每个级别。所以差异归结为k元search树的k / ln（k）。这在e = 2.7处具有最小值，并且k = 2提供最佳结果。