Is fibonacci search faster than binary search?

Question

I read some materials that claims Fibonacci search is faster than binary search on average,and the main cause is "it involves only addition and subtraction,not division by 2".

I have some questions:

1.Is Fibonacci search faster than binary search without regard to the operational speed?As the steps binary search take are less.

2.The division by 2 can be done by bit - shift operation,is it really slower than addition?

3.What's the advantage of Fibonacci search compared with binary search?

Answer 1

Is Fibonacci search faster than binary search without regard to the operational speed?As the steps binary search take are less.

It depends, on the underlying storage system for the list. For example - think of a disk. It is much 'cheaper' to look for a location in the same cylinder of the previously read one - since the reading arm does not have to move. So, if your reads are much closer to each other - you are more likely to need to move the reading arm less - so the expected time of each disk-seek is shorter. Also, to move the reading arm across less cylinders is similarly faster than moving it across more cylinders

In the example:

It is much cheaper to move the reading arm from (1) to (2) than it is from (1) to (3). And since (2) is 'closer' (in term of addresses) then (3), shorter jumps are more likely to be in this category. [From (1) to (2) the reading arm won't move at all, it will only let the disk spin until it reaches it]

The division by 2 can be done by bit - shift operation,is it really slower than addition?

This is mainly a hardware (and compiler optimization) issue. I cannot imagine any reason why a manufacture won't make this optimization, and bit-shift in most implementation I am aware of is as fast as additions.

What's the advantage of Fibonacci search compared with binary search?

As mentioned in (1) - shorter distance between consecutive disk seeks results in shorter (expected) seek times.

Answer 2

Additions, subtractions and divisions by 2 all take a single clock. So the arithmetic involved does not favor Fibonacci, on the opposite.

And you will need about 44% more lookups with Fibonacci (Log(2)/Log(Phi) - 1). Difficult to compensate by faster memory accesses !

If you are looking for alternatives to binary search, try your luck with interpolation search. http://en.wikipedia.org/wiki/Interpolation_search