Manolis Lourakis

Institute of Computer Science,

Foundation for Research and Technology - Hellas,

Heraklion, Crete, Greece

*Last updated Dec. 21, 2005*

*Fibonaccian search*, also referred to as *Fibonacci search*, is a divide-and-conquer algorithm for searching
a sorted array by narrowing possible locations to progressively smaller intervals. These intervals are determined
with the aid of the Fibonacci numbers. Note,
however, that the term Fibonacci search is also used to describe a technique that locates the minimum of a unimodal
function in a given interval (see this,
for example); this page is **not** concerned with that problem.

This page provides a C implementation of the Fibonaccian search algorithm, as defined above. The Fibonaccian search algorithm has time complexity of O(log(n)) and, due to its access pattern for the array elements, is much faster compared to the traditional binary search when the arrays being searched are large. In such cases, the cost of reading array elements depends critically on the dispersion of their storage locations, since reads involving large “jumps” in the array require considerably more time to complete. Typical examples include searching magnetic tapes and large arrays that do not fit in cache or RAM. The Fibonaccian search algorithm is quite old: a description of it in CACM dates back to 1960. Surprisingly though, I've been unable to find a public C implementation for it, that's why I have set up this page. The source code included here is distributed under the GNU General Public License (GPL).

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

- Set k = m.
- If k = 0, finish - no match.
- Test item against entry in position F
_{k-1}. - If match, finish.
- If item is less than entry F
_{k-1}, discard entries from positions F_{k-1}+ 1 to n. Set k = k - 1 and go to 2. - If item is greater than entry F
_{k-1}, discard entries from positions 1 to F_{k-1}. Renumber remaining entries from 1 to F_{k-2}, set k = k - 2 and go to 2.

If n is not a Fibonacci number, then let F_{m} be the smallest such number >n, augment the
original array with F_{m}-n numbers larger than the sought item and apply the above algorithm
for n'=F_{m}.

A C implementation of the Fibonaccian search algorithm is shown below. You can scroll through it while keeping the above pseudocode visible.

*Dec. 21, 2005:* Comments in `fibsrch.c` were slightly modified to bring them in sync with the code.

The source code is distributed in a gzip'ed tar file. It has been tested under linux with
gcc/lcc and under windows with MSVC.
Refer to the end of `fibsrch.c` for an example of using `fibsrch()`; remember to include `fibsrch.h` before
calling it from your code.

hits since Mon Dec 5 15:06:24 EET 2005 |