斐波那契查找

1 查找思想
设查找表中的记录数比某个Fibonacci数小1，即设n=F(j)-1。用Low、High和Mid表示待查找区间的下界、上界和分割位置，初值为Low=1，High=n。
⑴ 取分割位置Mid：Mid=F(j-1) ；
⑵ 比较分割位置记录的关键字与给定的K值：
① 相等： 查找成功；
② 大于：待查记录在区间的前半段(区间长度为F(j-1)-1)，修改上界指针： High=Mid-1，转⑴ ；
③ 小于：待查记录在区间的后半段(区间长度为F(j-2)-1)，修改下界指针：Low=Mid+1，转⑴ ；
直到越界(Low>High)，查找失败。
2 算法实现
在算法实现时，为了避免频繁计算Fibonacci数，可用两个变量f1和f2保存当前相邻的两个Fibonacci数，这样在以后的计算中可以依次递推计算出。
int fib(int n)
{ int i, f , f0=0 , f1=1 ;
if (n==0) return(0) ;
if (n==1) return(1) ;
for (i=2 ; i<=n ; i++ )
{ f=f0+f1 ; f0=f1 ; f1=f ; }
return(f) ;
}
int Fib_search(RecType ST[] , KeyType key , int n)
/* 在有序表ST中用Fibonacci方法查找关键字为key的记录 */
{ int Low=1, High, Mid, f1, f2 ;
High=n ; f1=fib(n-1) ; f2=fib(n-2) ;
while (Low<=High)
{ Mid=Low+f1-1;
if ( EQ(ST.[Mid].key, key) ) return(Mid) ;
else if ( LT(key, ST.[Mid].key) )
{ High=Mid-1 ; f2=f1