Programming Praxis

An interesting variant on binary search is Fibonacci search. Invented by Jack Kiefer in 1953 to find the zeros of a function, and first applied to searching in an array by David Ferguson in 1960, its initial appeal was to improve locality when searching for a record on magnetic tape. It was later applied to searching on paged memory when it was expensive to read a segment of an array from disk, and it is now used to improve locality of cache memory; a good idea never goes away! Here is a description of Fibonacci search, taken from Wikipedia:

Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. To test whether an item is in a list of n ordered numbers, proceed as follows:

1) Set k = m, where Fm is the smallest Fibonacci number greater than or equal to n.
2) If k = 0, halt and report failure.
3) Test item against entry in position Fk-1.
4) If match, halt and report success.
5) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n. Set k = k – 1 and go to 2.
6) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. Renumber remaining entries from 1 to Fk-2, set k = k – 2 and go to 2.

Your task is to implement Fibonacci search. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2