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.