|
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
////// but WITHOUT ANY WARRANTY; without even the implied warranty of
////// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
////// GNU General Public License for more details.
//////
///////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "fibsrch.h"
/*
* If val is found in arr, return the index of its location in arr.
* Otherwise, return the index of the smallest element greater than val
*/
static int binsrch_geq(const int *arr, int n, int val)
{
register int low, high, mid;
int geq;
low=0; high=n-1; geq=-1;
/* binary search for finding the element with value val */
while(low<=high){
mid=(low+high)>>1; //(low+high)/2;
if(val<arr[mid]){
high=mid-1;
geq=mid;
}
else if(val>arr[mid])
low=mid+1;
else
return mid; /* found */
}
return geq; /* not found */
}
/*
Fibonaccian search for locating the index of "val" in an array "arr" of size "n"
that is sorted in ascending order. See http://doi.acm.org/10.1145/367487.367496
Algorithm description
-----------------------------------------------------------------------------
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:
a) Set k = m.
b) If k = 0, finish - no match.
c) Test item against entry in position Fk-1.
d) If match, finish.
e) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n.
Set k = k - 1 and go to b).
f) 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 b)
If Fm>n then the original array is augmented with Fm-n numbers larger
than val and the above algorithm is applied.
*/
int fibsrch(const int *arr, int n, int val)
{
register int k, idx, offs;
static int prevn=-1, prevk=-1;
/* Precomputed Fibonacci numbers F0 up to F46. This implementation assumes that the size n
* of the input array fits in 4 bytes. Note that F46=1836311903 is the largest Fibonacci
* number that is less or equal to the 4-byte INT_MAX (=2147483647). The next Fibonacci
* number, i.e. F47, is 2971215073 and is larger than INT_MAX, implying that it does not
* fit in a 4 byte integer. Note also that the last array element is INT_MAX rather than
* F47. This ensures correct operation for n>F46.
*/
const static int Fib[47+1]={0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578,
5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903, INT_MAX};
/* find the smallest fibonacci number that is greater or equal to n. Store this
* number to avoid recomputing it in the case of repetitive searches with identical n.
*/
if(n!=prevn){
#if 1
k=(n>1)? binsrch_geq(Fib, sizeof(Fib)/sizeof(int), n) : 1;
#else /* the above binary search call can be substituted by the following code fragment: */
{
register int f0, f1, t;
for(f0=0, f1=1, k=1; f1<n; t=f1, f1+=f0, f0=t, ++k)
;
}
#endif
prevk=k;
prevn=n;
}
else k=prevk;
/* If the sought value is larger than the largest Fibonacci number less than n,
* care must be taken top ensure that we do not attempt to read beyond the end
* of the array. If we do need to do this, we pretend that the array is padded
* with elements larger than the sought value.
*/
for(offs=0; k>0; ){
idx=offs+Fib[--k];
/* note that at this point k has already been decremented once */
if(idx>=n || val<arr[idx]) // index out of bounds or val in 1st part
continue;
else if (val>arr[idx]){ // val in 2nd part
offs=idx;
--k;
}
else // val==arr[idx], found
return idx;
}
return -1; // not found
}
#if 0
/* Sample driver program for fibsrch() */
main()
{
int data[]={1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30, 32, 33, 36, 39, 41, 44, 47, 51, 53, 55};
int i, x, n;
x=30; n=sizeof(data)/sizeof(int);
i=fibsrch(data, n, x);
if(i>=0)
printf("%d found at index %dn", x, i);
else
printf("%d was not foundn", x);
}
#endif |
