三分查找比二分查找更糟糕吗？

Question

人们通常会问相反的问题（三分查找比二分查找更好吗？）。

我真的认为它更差（不是从O(log n)的复杂度来看）。 我对数学并不擅长，只凭直觉。

如果我们使用二分查找来搜索大小为n的数组，第一次比较后，我们的问题规模就变成了n/2，第二次比较后，问题规模就缩小为n/4。

而当使用三分查找时，第一次循环就已经进行了两次比较！我们只剩下一个问题规模为n/3。

我的理解是否正确，还是我漏掉了什么？事实上，在我读到的所有资料中，人们通常认为三分查找的第一次循环只需要进行1次比较，这种想法我认为是错误的。

- Seth Keno

---

如果比较是1个操作，则：1 + 1 = 2 = c = c * 1，因此O(c * 1) = 1。 - Logan Murphy

只有程序员才能理解三元逻辑的美妙：真 + 假 + 文件未找到。 - Marc B

相关/可能重复 - 如果有三分查找，为什么要使用二分查找？ - Bernhard Barker

但是比较并不是一切。缓存一致性也很重要。搜索三叉树通常会导致更少的缓存未命中，而那些缓存未命中比几个额外的比较要昂贵得多。 - Jim Mischel

Answer 1

作为一种有趣的练习，让我们思考一下 "d-ary搜索"，其中您查看数组的 (d - 1) 个等间距元素，然后决定递归进入哪个 d 种不同的区间。 如果使用d-ary搜索，则每个点剩余的数组大小将是n、n / d、n / d²、n / d³、...、n / d^k，...。 这意味着递归中会有 log_dn 层。在每层中，您会进行恰好d - 1次比较。这意味着总共进行的比较次数是(d - 1)log_dn。对于任何固定值的d，这是O(log n)，尽管常数因子会有所不同。

使用二元搜索时，d = 2，比较次数将大约为(2 - 1)log₂n = log₂n。为简单起见，我们通过将其写为 ln n / ln 2 = 1.443 ln n 来将其写为自然对数。

使用三叉搜索时，d = 3，比较次数将大约为(3 - 1)log₃n = 2log₃n。将其写为自然对数，我们得到这是 2ln n / ln 3 = 1.820 ln n。因此，三叉搜索中的比较次数确实大于二元搜索中的比较次数，因此您可以预期它比二元搜索慢。事实上，正如 这篇文章指出的那样，在实践中就是这样。

希望这有所帮助！

- templatetypedef

---

您稍稍夸大了三叉搜索中比较的数量。在最坏情况下，“d-1”是最大比较次数；平均而言，您只需要进行“d/2”次比较。 - chepner

@chepner- 这是一个很好的观点。我考虑的是最坏情况，而不是平均情况，所以感谢你指出来！ - templatetypedef

我同意这个分析，但是有些情况下三分搜索更好。文章中提到的病态缓存行为与内存缓存不完全关联有关。因此，单个缓存位置只能保存来自少量内存地址的缓存行。因此，在二分搜索大小为2的幂的数组时，可能会出现可怕的缓存性能问题。 - davidmw