Fibonacci Search

May 12, 2015

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

2 Responses to “Fibonacci Search”

  1. matthew said

    If n is the size of the input, then since Fibonacci numbers increase exponentially, surely it’s only log(n) time (or faster) to find the first one greater or equal to n.

    The Knuth variant on the Wikipedia page looks fun.

  2. matthew said

    So here it is, it makes a nice tail-recursive function with the position in the array being examined being passed in directly as a pointer:

    #include <stdio.h>
    #include <stdlib.h>
    
    int *find(int t, int *a, int p, int q) {
      return 
        t < *a? q == 0? 0: find(t,a-q,q,p-q)     // Down one
       :t > *a? p == 1? 0: find(t,a+q,p-q,2*q-p) // Down two
       :a;
    }
    
    int main(int argc, char *argv[])
    {
      int n = atoi(argv[1]), p = 1, q = 0;
      for (int i = 0; i < n; i++) {
        p = p+q; q = p-q;
      }
      int N = p+q-1;
      int a[N];
      for (int i = 0; i < N; i++) {
        a[i] = i;
      }
      for (int i = 0; i < N; i++) {
        int *j = find(i,a+p-1,q,p-q);
        printf("%d %d\n",i,*j);
      }
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: