fibsrch: Fibonaccian search in C

Manolis Lourakis
Institute of Computer Science,
Foundation for Research and Technology - Hellas,
Heraklion, Crete, Greece

Last updated Dec. 21, 2005

[ The Algorithm :: Highlighted Source Code :: What's new? :: Download Code :: Contact Address ]

*NEW*: version 1.1 is out!

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).

The Algorithm

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 = Fm ordered numbers, proceed as follows:

  1. Set k = m.
  2. If k = 0, finish - no match.
  3. Test item against entry in position Fk-1.
  4. If match, finish.
  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.

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

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

Highlighted Source Code

What's new?

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

Download 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.

Contact Address

If you find this code useful or have any comments/questions/suggestions, please contact me at .

[ The Algorithm :: Highlighted Source Code :: What's new? :: Download Code :: Contact Address ]

hits since Mon Dec 5 15:06:24 EET 2005 Firefox: take back the web!