///////////////////////////////////////////////////////////////////////////////////////
//////
//////  Fibonaccian search in an ordered array
//////  Copyright (C) 2005 Manolis Lourakis (lourakis AT .DeleteThis.ics.forth.gr)
//////  Institute of Computer Science, Foundation for Research & Technology - Hellas
//////  Heraklion, Crete, Greece.
//////
//////  This program is free software; you can redistribute it and/or modify
//////  it under the terms of the GNU General Public License as published by
//////  the Free Software Foundation; either version 2 of the License, or
//////  (at your option) any later version.
//////
//////  This program is distributed in the hope that it will be useful,
//////  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 *arrint nint val)
{
register int lowhighmid;
int geq;

low=0high=n-1geq=-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 *arrint nint val)
{
register int kidxoffs;
static int prevn=-1prevk=-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]={011235813213455891442333776109871597258441816765,
1094617711286574636875025121393196418317811514229832040134626921783093524578,
5702887922746514930352241578173908816963245986102334155165580141267914296,
43349443770140873311349031701836311903INT_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(Fibsizeof(Fib)/sizeof(int), n) : 1;
#else /* the above binary search call can be substituted by the following code fragment: */
{
register int f0f1t;

for(f0=0f1=1k=1f1<nt=f1f1+=f0f0=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=0k>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[]={14579111316182025273032333639414447515355};
int ixn;

x=30n=sizeof(data)/sizeof(int);
i=fibsrch(datanx);
if(i>=0)
printf("%d found at index %d\n"xi);
else
printf("%d was not found\n"x);
}
#endif