黄金分割搜索比二分查找更好吗？

最近我听到一种观点，认为二进制搜索可以通过用phi（黄金定额）而不是2来分割范围来改进。这对我来说是一个很大的惊喜，因为我从来没有听说过这种优化。这是真的？如果除以2和phi的性能是同样的，那么这会是真的吗？黄金分割搜索比二分查找更好吗？

如果没有，是否有任何一般条件下的黄金分割搜索会比二分查找更快？

UPD：编辑删除链接到一个不相关的维基百科文章。对不起，误导。

2010-11-22 Fixpoint

有两种算法叫做“斐波那契搜索”。

The article you linked是关于找到某些函数的最大值或最小值的数值算法。这是这个问题的最佳算法。这个问题与二分查找问题的不同之处在于，对于任何合适的情况，它都应该是显而易见的。

The other kind of Fibonacci search的确会攻击与二分查找相同的问题。二进制搜索本质上总是更好。 Knuth写道，斐波那契搜索“在某些计算机上更好，因为它只涉及加法和减法，而不是2除法”。但几乎所有计算机都使用二进制算术，其中2除以比加减简单。

（维基百科的文章目前声称，斐波那契搜索可以有更好的参考局部性，索赔克努特确实不作。它可以，也许，但是这是一种误导。通过斐波纳契搜索所做的测试更接近在一定程度上它们对于缩小范围的帮助不大;平均而言，这将导致更多的表的读取次数不会更少，如果记录实际存储在磁带上，那么搜索次数占主导地位，那么斐波那契搜索可能击败二进制搜索—但在这种情况下，两种算法远远没有达到最佳。）

来源

2010-11-22 16:24:00

“作品更快”是模糊的;但二进制搜索应具有访问次数最低的最差情况。

来源

2010-11-22 15:49:57 lijie

中，其中歪斜划分区域将有更多的任何方法当搜索到的项目在更大的区域结束时访问。平均情况可能会下降，但最糟糕的情况会上升。编码中的类似概念（香农意义上的）。 – lijie 2010-11-22 15:52:59

...来扩展最后一个音符 - 并且当搜索到的项目更倾向于在更小的区域中更频繁地找到时，偏斜的方法平均会更好。根据对数据性质的一些了解，如果你有一个很好的方法来决定哪一边应该更小，这只会发生。 – greggo 2014-02-13 01:20:27

我在这里可能会丢失一些东西，但在黄金分割搜索中查看维基百科条目之后，它似乎并没有像二分查找那样解决同样的问题。二进制搜索对于在排序列表中查找值非常有用，而黄金分段搜索则用于在一系列值中查找函数的最小值或最大值。

来源

2010-11-22 15:54:03 Ferruccio

正确，它们用于不同的目的，并且在不同的条件下是最佳的。二分法用于查找“根”或某处属性发生变化的位置，并且对于精炼“包围对”（符号（属性）不同的位置对）最合适。黄金分割搜索用于最小化/最大化，并且对于细化“包围三元组”，三元组a，b，c使得a mokus 2010-11-22 16:12:47

黄金分割搜索比二分查找更好吗？

回答

相关问题