Is golden section search better than binary search?

Question

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: Edited to remove link to a non-relevant Wikipedia article. Sorry for misleading.

Solution 1

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.

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.

(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.)

Solution 2

I may be missing something here, but after looking at the Wikipedia entry on the golden section search it seems like it doesn't solve the same problem as a binary search at all. Whereas a binary search is useful for finding a value in a sorted list, a golden section search is used to find a minimum or maximum value of a function over a range of values.

Solution 3

"works faster" is vague; but binary search should have the lowest worst case bound for number of accesses.

Comments

[lijie]

as in, any method which skews the divided region will have more accesses when the searched-for item ends up in the larger region. The average case may go down, but the worst case will go up. Similar concepts in coding (in the Shannon sense).

[mokus]

Correct, they are for different purposes and optimal under different conditions. Bisection is for finding "roots", or places where some property changes, and is optimal for refining "bracketing pairs" - pairs of locations for which the sign (property) differs. Golden section search is for minimization/maximization, and is optimal for refining "bracketing triplets", triples of points a,b,c such that a < b < c and f(b) < f(a) and f(b) < f(c). Which you should be using depends on the nature of whatever you're searching for.

[Piotr Dobrogost]

Instead of hand waving it would be better to let us know complexities of Fibonacci search which are missing in the Wikipedia's article (there's only one complexity given and this is without saying what's type it is - useless information).

[Jason Orendorff]

The differences are constant-factor. In random-access memory, Binary search and Fibonacci search are both O(log n). When searching a tape, both are O(n).

[greggo]

... to extend that last note - and the skewed method will be better on average when the searched-for item tends to be more often found in the smaller region. Which is only going to happen if you have a good way of deciding which side should be smaller, based on some knowledge of the nature of the data.