如果有三元搜索，为什么还要使用二进制搜索？

Question

最近，我听说过三元搜索，其中我们将阵列分为3个部分并进行比较。这里将进行两个比较，但将数组降低到N/3。人们为什么不使用太多？

Answer 1

实际上，人们确实使用k-ary树作为任意k。

但是，这是一个权衡。

要在K-ary树中找到一个元素，您需要围绕k*ln（n）/ln（k）操作（请记住基本公式）。您的K越大，您需要的整体操作就越多。

您所说的逻辑扩展是“为什么人们不为n个数据元素使用n-ary树？”。当然，这将是一个数组。

Answer 2

三元搜索仍然会给您相同的渐近复杂性 o（log n） 搜索时间，并为实现增加了复杂性。

可以说为什么您不需要四Quad搜索或任何其他更高订单。

Answer 3

与二进制搜索相比，搜索10亿（美国十亿 -1,000,000,000个分类的物品比较约15个，大约9个与三元搜索进行比较 - 不是一个巨大的优势。并请注意，每个“三元比较”可能涉及2个实际比较。

Answer 4

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

您的CPU不支持三元逻辑作为单个操作；它将三元逻辑分为二进制逻辑的几个步骤。 CPU的最佳代码是二进制逻辑。如果芯片很常见，将三元逻辑作为单个操作支持，那么您是对的。

B树可以在每个节点上有多个分支；订单3 b-Tree是三元逻辑。沿着树的每个步骤将进行两个比较，而不是一个比较，这可能会导致CPU时间较慢。

但是，B树非常普遍。如果您假设树中的每个节点都会在磁盘上单独存储在某个地方，那么您将花费大部分时间从磁盘上阅读...而CPU不会是瓶颈，但是磁盘将是。因此，您将每个节点有100,000个孩子或其他任何东西都带有B-Tree 仅仅 适合一个内存的一个块。具有这种分支因子的B树很少会超过三个节点，并且您只有三个磁盘读取 - 瓶颈上的三个站点 - 搜索一个巨大的，巨大的数据集。

评论：

• 硬件不支持三元树，因此它们的运行速度较低。
• b肌的订单大得多，大得多3是大型数据集的磁盘优化的常见；一旦您超越了2，就会超过3。

Answer 5

三元搜索的唯一方法比二进制搜索更快的方法是，如果可以进行三路分区确定的确定速度小于2速比较成本的1.55倍。如果将项目存储在排序的阵列中，则三向确定的平均为1.66倍，是2向确定的贵倍。但是，如果信息存储在树上，则获取信息的成本相对于实际比较的成本很高，并且缓存局部性意味着随机获取一对相关数据的成本并不比获取单个数据的成本差得多基准，三元或N向树可能会大大提高效率。

Answer 6

是什么让您认为三元搜索应该更快？

平均比较数：

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

因此，看起来三元搜索更糟。

Answer 7

另外，请注意，如果我们继续前进，此序列将概括为线性搜索

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

因此，在N-ary搜索中，我们将拥有“唯一的比较”，这可能需要直到n个实际比较。

Answer 8

在最佳情况下，“ terinary”（三元？）搜索更有效，这涉及搜索第一个元素（或者最后一个元素，具体取决于您首先进行的比较）。对于距离末端的元素，您首先要检查，而两个比较每次将数组缩小2/3，与二进制搜索的两个比较相同，将搜索空间缩小3/4。

此外，二进制搜索更简单。您只需比较并获得一半或另一个，而不是比较，如果比第一三分之一，则比较，如果少于获得第二三分之一，则获得最后三分之一。

Answer 9

三元搜索可以有效地用于并行体系结构-FPGA和ASIC。例如，如果搜索所需的内部FPGA内存小于FPGA资源的一半，则可以制作重复的内存块。这将允许同时访问两个不同的内存地址，并在单个时钟周期中进行所有比较。这就是100MHz FPGA有时能够胜过4GHz CPU的原因之一:)

Answer 10

这是 一些我根本没有审查的随机实验证据 表明它比二进制搜索慢。

Answer 11

二进制搜索树上几乎所有的教科书和网站都没有真正谈论二进制树！他们向您展示三元搜索树！真正的二进制树将数据存储在其叶子中，而不是内部节点（除了导航的密钥外）。有些人称这些叶树，并区分教科书中显示的节点树：

J. Nievergelt，C.-K。 Wong：二元树总路径长度的上限，杂志ACM 20（1973）1-6。

以下内容来自彼得·布拉斯（Peter Brass）关于数据结构的书。

2.1搜索树的两种型号

在刚刚给出的轮廓中，我们倾向于一个重要的观点，即一开始似乎很微不足道，但实际上它导致了两种不同的搜索树模型，这两种模型都可以与以下许多材料结合在一起，但其中一种是非常可取的。

如果我们在每个节点中比较查询键与节点中包含的键，如果查询键较小，并且如果查询键较大，则遵循左分支，那么如果查询键更大，那么如果它们相等，会发生什么？搜索树的两种模型如下：

1. 如果查询键小于节点键，请左分支；否则，请沿正确的分支，直到到达树的一片叶子为止。树的内部节点中的键仅用于比较。所有物体都在叶子中。

2. 如果查询键小于节点键，请左分支；如果查询密钥大于节点键，请拿正确的分支；如果节点相等，则将包含在节点中的对象中。

这个小点有许多后果：

{在模型1中，基础树是二进制树，而在模型2中，每个树节点实际上是一个带有特殊中间邻居的三元节点。

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

因此，模型1的搜索树的结构比模型2的树的结构更规则。至少对于实施而言，这是一个明显的优势。

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

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

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

这很容易看到，因为H的高度H具有左右子树的最多为H -1的高度树，并且在模型2中，它们之间的另一个对象。

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

在模型1中，甚至可能有可能使用任何对象的键，例如，如果对象已删除。通过从概念上将比较和识别的这些功能分开，这并不奇怪，在以后的结构中，我们甚至可能需要定义与任何对象相对应的人工测试，只是为了获得搜索空间的良好划分。用于比较的所有键都必须与众不同，因为在Model 1树中，每个内部节点都有非空的左右子树。因此，每个密钥最多发生两次，一次是比较键，一次是叶片中的识别键。

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

Answer 12

您可能已经听说过那些涉及权衡尺度上事物的谜语中使用的三元搜索。这些量表可以返回3个答案：左较轻，两者都是相同的，或者左较重。因此，在三元搜索中，只需进行1个比较。但是，计算机使用布尔逻辑，只有2个答案。要进行三元搜索，您实际上必须进行2个比较，而不是1。我想在某些情况下，这种情况仍然像以前提到的海报一样快，但是您可以看到三元搜索并不总是更好，而且它是在计算机上实施更令人困惑，更自然。

Answer 13

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

Answer 14

我刚刚发布了 博客 关于三元搜索，我显示了一些结果。我还提供了一些初始级别的实现 Git Repo 我完全同意关于三元搜索理论部分的每个人，但是为什么不尝试一下呢？根据实施，如果您有三年的编码经验，则该部分很容易。我发现，如果您有庞大的数据集，并且需要多次搜索三元搜索具有优势。如果您认为可以通过三元搜索做得更好。

Answer 15

尽管您在两个搜索树中都获得了相同的Big-O复杂性（LN N），但差异在于常数。您必须对每个级别的三元搜索树进行更多比较。因此，差异归结为k/ln（k）的k-ary搜索树。在E = 2.7和K = 2时，其最小值提供了最佳结果。