Fibonacci Search
May 12, 2015
Let’s begin by implementing a basic binary search, which returns the zero-based index of x in xs, or -1 if x is not found:
(define (bsearch lt? x xs)
(let ((len (vector-length xs)))
(let loop ((lo 0) (hi (- len 1)))
(if (< hi lo) -1
(let ((mid (quotient (+ lo hi) 2)))
(cond ((lt? x (vector-ref xs mid))
(loop lo (- mid 1)))
((lt? (vector-ref xs mid) x)
(loop (+ mid 1) hi))
(else mid)))))))
> (define ps '#(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47))
> (bsearch < 23 ps)
8
> (bsearch < 45 ps)
-1
> (filter (lambda (x) (not (negative? x)))
(map (lambda (p) (bsearch < p ps)) (range 50))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
Now we implement Fibonacci search, initializing k by linear search through the fibs vector, which is about as bad as it sounds:
(define fib ; (fib n) returns nth fibonacci number, n < 52
(let ((fibs (let loop ((k 50) (fibs (list 1 0)))
(if (zero? k) (list->vector (reverse fibs))
(loop (- k 1) (cons (+ (car fibs) (cadr fibs)) fibs))))))
(lambda (n) (vector-ref fibs n))))
(define (fsearch lt? x xs)
(let* ((len (vector-length xs))
(k (do ((k 0 (+ k 1)))
((<= len (fib k)) (- k 1)))))
(let loop ((lo 0) (hi (- len 1)) (k k))
(if (not (positive? k)) -1
(let ((mid (min (+ lo (fib (- k 1))) hi)))
(cond ((lt? x (vector-ref xs mid))
(loop lo mid (- k 2)))
((lt? (vector-ref xs mid) x)
(loop mid hi (- k 1)))
(else mid)))))))
The overall structure here is the same as binary search, which is why we began by implementing binary search; the loop sets lo and hi, there is a test for completion of a failed search, a midpoint is computed, and a three-way comparison is performed. The differences are the computation of the midpoint, which is based on Fibonacci numbers rather than division by two, and the test for a failed search. The “renumber remaining entries” step is performed by adjusting lo. Here are some examples:
> (fsearch *lt; 23 ps)
8
> (fsearch *lt; 45 ps)
-1
> (filter (lambda (x) (not (negative? x)))
(map (lambda (p) (fsearch *lt; p ps)) (range 50))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
Fibonacci search is impractical because of the time required to initialize k; we used an O(n) algorithm, and there’s an obvious O(log n) algorithm for initializing k, but you don’t want to do either of those in the inner loop of a function that is called millions of times. Ignoring Fibonacci numbers for a moment, the search method is basically binary search but with the search space being reduced by the gap between successive Fibonacci numbers, which in the limit is φ = (1 + √5) / 2 ≈ 1.6180339887, instead of being halved as in binary search. Thus, instead of using fibonacci numbers, we can just use φ, which leads to golden section search:
(define (gsearch lt? x xs)
(define (gsection lo hi)
(let ((phi (/ (+ 1 (sqrt 5)) 2)))
(+ (inexact->exact (round
(/ (- hi lo) phi))) lo)))
(let ((len (vector-length xs)))
(let loop ((lo 0) (hi (- len 1)))
(if (< hi lo) -1
(let ((mid (gsection lo hi)))
(cond ((lt? x (vector-ref xs mid))
(loop lo (- mid 1)))
((lt? (vector-ref xs mid) x)
(loop (+ mid 1) hi))
(else mid)))))))
The only difference between the golden section search and binary search is that the midpoint is computed by dividing by φ instead of dividing by 2. Here are some examples:
> (gsearch < 23 ps)
8
> (gsearch < 45 ps)
-1
> (filter (lambda (x) (not (negative? x)))
(map (lambda (p) (gsearch < p ps)) (range 50))
(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
Both Fibonacci search and golden section search take time O(log n), the same as binary search, though they make more comparisons on average than binary search. Whether or not that leads to improved search times depends on how long it takes to access an element of an array and how long it takes to perform a comparison. Personally, I think I’ll stay with binary search.
You can run the program at http://ideone.com/mVidsi.
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); } }