Is fax search faster than binary search?

Question

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

I have a few questions:

1. Fibonacci searches are faster than binary searches, regardless of speed. Since binary search steps are smaller,

2. Division by 2 can be performed using the bit-shift operation, is it really slower than adding?

3. What is the advantage of a Fibonacci search over binary search?

Answer 1

Is a Fibonacci search faster than a binary search without considering the speed of work? Since binary search steps are smaller, smaller.

It depends on the underlying storage system for the list. For example, think of a disk. It is “cheaper” to look for a place in the same cylinder that was previously read, since the reader should not move. Thus, if your readings are much closer to each other, you will most likely need to move the reader less, so the expected time of each disk search is shorter. In addition, moving the read arm across the cylinders is less than moving it over a larger number of cylinders.

In the example:

It is much cheaper to move the reader from (1) to (2) than from (1) to (3). And since (2) is “closer” (in terms of addresses), then (3), shorter jumps are likely to be in this category. [From (1) to (2) the read arm will not move at all, it will only rotate the disc until it reaches it]

Division by 2 can be done using the bit-shift operation, is it really slower than adding?

This is mainly a hardware (and compiler optimization) issue. I can not imagine any reason why production will not do this optimization, and I know the bit-shift in the majority of implemented ones as fast as the additions.

What is the advantage of a Fibonacci search over binary search?

As mentioned in (1), a shorter distance between consecutive disk images leads to shorter (expected) search times.

Answer 2

Additions, subtractions and divisions by 2 all take one beat. Thus, the participating arithmetic does not support Fibonacci, on the contrary.

And you will need about 44% of the queries using Fibonacci ( Log(2)/Log(Phi) - 1 ). Hard to compensate for faster memory access!

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