是黄金分割比搜索二进制搜索更好？ [英] Is golden section search better than binary search?

问题描述

最近我听说，而不是按2。这是一个很大的惊喜，我的意见是二进制搜索可能会采取通过拆分由岛（金比）的范围内得到改善，因为我从来没有听说过这样的优化。这是真的？请问这是真实的，如果按2和披师同样高性能的？

Recently I've heard an opinion that binary search may be improved by taking by splitting the range by phi (golden ration) instead of by 2. This was a big surprise to me, because I've never heard about such optimization. Is this true? Would this have been true if division by 2 and by phi was equally performant?

如果不是，是否有下黄金分割搜索将超过二分查找更快地执行任何的一般条件？

If not, are there any general conditions under which golden section search would perform faster than binary search?

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

UPD: Edited to remove link to a non-relevant Wikipedia article. Sorry for misleading.

推荐答案

有两种算法称为斐波那契搜索。

There are two algorithms called "Fibonacci search".

您链接这篇文章是关于一个数值算法寻找某些功能的最大或最小。正是由于这个问题的最优算法。这个问题是刚好足够不同于二进制搜索问题，即应该是显而易见的任何给定的情况下，这是适当的。

The article you linked is about a numerical algorithm for finding the maximum or minimum of certain functions. It is the optimal algorithm for this problem. This problem is just different enough from the binary search problem that it should be obvious for any given case which is appropriate.

另一种斐波那契搜索的的确攻击同一个问题，因为二进制搜索。二进制搜索本质上是总是更好。克努特写道，斐波那契搜索是在某些计算机preferable，因为它只涉及加法和减法，而不是除以2。但是，几乎所有的计算机都使用二进制算术，其中除以2的简单的比加法和减法。

The other kind of Fibonacci search does attack the same problem as binary search. Binary search is essentially always better. Knuth writes that Fibonacci search "is preferable on some computers, because it involves only addition and subtraction, not division by 2." But almost all computers use binary arithmetic, in which division by 2 is simpler than addition and subtraction.

（Wikipedia文章目前声称，斐波那契搜索可能有更好的局部性参考，索赔克努特确实的没有的制作，它的可以的，也许，但是这是一种误导。由斐波搜索所做的试验是更靠近在一起precisely到它们在缩小范围少有益的程度;平均这将导致从该表，而不是更少如果这些记录的多个部分的多读取。实际上存储在磁带上，从而使寻道时间占据主导地位，那么斐波那契搜索可能击败二进制搜索＆mdash;但在这种情况下，两种算法都远非最佳）

(The Wikipedia article currently claims that Fibonacci search could have better locality of reference, a claim Knuth does not make. It could, perhaps, but this is misleading. The tests done by a Fibonacci search are closer together precisely to the extent that they are less helpful in narrowing down the range; on average this would result in more reads from more parts of the table, not fewer. If the records are actually stored on tape, so that seek times dominate, then Fibonacci search might beat binary search—but in that case both algorithms are far from optimal.)

这篇关于是黄金分割比搜索二进制搜索更好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！