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

Question

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

algorithmdata-structuresbinary-treeternary-tree

43

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

- mousey

3

如果数组只有两个元素会怎样？ - Carlos Muñoz

13

这是一个特殊情况。 - mousey

1

令人惊讶的是，所有答案都只谈到时间复杂度。在许多情况下，空间复杂度同样重要，三叉树通常更具空间效率。(而且，考虑到现代CPU架构，空间复杂度经常对实际性能产生重大影响)。 - Ian Mercer

1

我很感激这个6年前的问题。你所描述的不是三分搜索，请问有人可以编辑标题吗？FYI，三分搜索适用于单峰函数，而二分搜索适用于单调函数。 - marcv81

我觉得奇怪的是没有人提到问题的假设是错误的这一事实。它并不将数组缩小到 n/3，而是缩小到三分之二，这意味着比二分搜索留下更多元素。另一方面，这两种算法的目的完全不同。三分搜索用于查找单峰函数的最小/最大值，而二分搜索算法无法完成此任务。 - Chris Vilches

15个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steven Schlansker · Answer 1

1

这里有一些随意的实验证据，我还没有进行任何审查，表明它比二分查找要慢。

- Steven Schlansker

1

权限被拒绝：“此博客仅对受邀读者开放。http://e-hon.blogspot.com/ 看起来您没有被邀请阅读此博客。如果您认为这是一个错误，您可以联系博客作者并请求邀请。” - Ali Essam

- Crashh · Answer 2

尽管在搜索树中，你可以得到相同的大O复杂度（ln n），但区别在于常数。在每个层级上，三叉搜索树需要进行更多的比较。因此，差异归结为k/ln(k)对于k元搜索树。这在e=2.7时具有最小值，而k=2提供了最佳结果。

- muddybruin · Answer 3

你可能听说过三分查找算法，它通常被用在那些需要用天平称重的谜题中。这种天平会有3种结果：左边轻，两边一样重，或左边重。所以在三分查找中，只需要进行1次比较。然而，计算机使用的是布尔逻辑，只有2种结果。为了进行三分查找，实际上需要进行2次比较。我想有些情况下这依然比其他方法更快，正如之前的评论者所提到的，但是你可以看出，三分查找并不总是更好，在计算机上实现起来也更加混乱和不自然。

- Daniel · Answer 4

理论上，k/ln(k) 的最小值在 e 处达到，由于 3 比 2 更接近 e，因此需要更少的比较。你可以验证 3/ln(3) = 2.73.. 和 2/ln(2) = 2.88..。二分查找之所以可能更快，是因为其代码将具有更少的分支，并且在现代 CPU 上运行速度更快。

- Vraj Pandya · Answer 5

我刚刚发布了一篇有关三分查找的博客，并展示了一些结果。我还在我的git库上提供了一些初级实现。我完全同意每个人对三分查找理论部分的看法，但为什么不试一试呢？根据实现来看，如果你有三年的编程经验，那部分是足够容易的。我发现，如果你有一个庞大的数据集，并且需要多次搜索它，那么三分查找有优势。如果你认为你可以用三分查找做得更好，那就去试试吧。