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.
Programming Praxis 
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.
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); } }