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