Fix*_*int 9 algorithm search binary-search
最近我听说有一种观点认为二元搜索可以通过将范围分为phi(黄金比例)而不是2来改进.这对我来说是一个很大的惊喜,因为我从来没有听说过这样的优化.这是真的？如果按2和按照phi分算同样有效,那么这是真的吗？
如果没有,是否有任何一般条件,黄金分割搜索比二分查找更快？
UPD:已编辑删除与不相关的维基百科文章的链接.很抱歉误导.
有两种称为"Fibonacci搜索"的算法.
您链接的文章是关于查找某些函数的最大值或最小值的数值算法.它是解决此问题的最佳算法.这个问题与二元搜索问题完全不同,对于任何适当的给定情况,它应该是显而易见的.
另一种斐波纳契搜索确实攻击了与二进制搜索相同的问题.二进制搜索基本上总是更好.Knuth写道,Fibonacci搜索"在某些计算机上更可取,因为它只涉及加法和减法,而不是2除法." 但几乎所有的计算机都使用二进制算术,其中除以2 比加法和减法更简单.
(维基百科的文章目前声称,斐波那契搜索可以有更好的参考局部性,索赔克努特并没有做出,这可能,也许,但是这是一种误导.由斐波那契搜索所做的测试中更靠近在一起恰恰是他们的程度在缩小的范围内帮助较小;平均,这将导致更多的从表中的多个部分读取,而不是更少.如果记录实际上是存储在磁带上,从而使寻道时间占据主导地位,那么斐波那契搜索可能击败二进制搜索,但在这种情况下,两种算法都不是最优的.)
我可能在这里遗漏了一些东西，但在查看了黄金分割搜索的维基百科条目后，它似乎根本无法解决与二分搜索相同的问题。二分搜索可用于在排序列表中查找值，而黄金分割搜索用于在值范围内查找函数的最小值或最大值。