最近我听到一个观点，二进制搜索可以通过将范围划分为 phi（黄金比例）而不是 2 来改进。这对我来说是一个很大的惊喜，因为我从未听说过这种优化。这是真的？如果除以 2 和除以 phi 的性能相同，这会是真的吗？
如果不是，是否存在黄金分割搜索比二分搜索执行得更快的一般条件？
UPD：已编辑以删除不相关的 Wikipedia 文章的链接。抱歉误导。
问问题
12636 次
3 回答
11
有两种算法称为“斐波那契搜索”。
您链接的文章是关于用于查找某些函数的最大值或最小值的数值算法。它是这个问题的最佳算法。这个问题与二分搜索问题有足够的不同，对于任何合适的给定情况都应该是显而易见的。
另一种斐波那契搜索确实解决了与二进制搜索相同的问题。二分搜索本质上总是更好。Knuth 写道，斐波那契搜索“在某些计算机上更可取，因为它只涉及加法和减法，而不是除以 2。” 但几乎所有计算机都使用二进制算术，其中除以 2比加减法更简单。
（维基百科文章目前声称斐波那契搜索可以具有更好的参考位置，Knuth没有提出这一说法。它可能，也许，但这是误导性的。斐波那契搜索所做的测试在某种程度上更接近，因为它们是对缩小范围的帮助较小；平均而言，这将导致从表的更多部分进行更多读取，而不是更少。如果记录实际上存储在磁带上，因此查找时间占主导地位，那么斐波那契搜索可能会击败二进制搜索——但是在那种情况下，这两种算法都远非最优。）
于 2010-11-22T16:24:00.360 回答
5
我可能在这里遗漏了一些东西，但是在查看了黄金分割搜索的 Wikipedia 条目之后，它似乎根本无法解决与二进制搜索相同的问题。二进制搜索可用于在排序列表中查找值，而黄金分割搜索用于查找函数在值范围内的最小值或最大值。
于 2010-11-22T15:54:03.780 回答
1
“工作得更快”是模糊的；但是二进制搜索应该具有访问次数的最低最坏情况界限。
于 2010-11-22T15:49:57.747 回答