转载

数据结构之斐波那契查找

数据结构之--斐波那契查找

定义:相当于折半查找,一般将带比较的key值与第mid=(low+high)/2位置的元素比较,比较结果分为三种情况:

1),相等,mid位置的元素即为所求;

2),>,low=mid+1;

3),<,high=mid-1;

跟折半查找很相似,它是根据斐波那契数列的特点对有序表进行黄金分割。

图解:

数据结构之斐波那契查找

时间复杂度:如果要查找的记录在右侧,则左边的数据都不用在哦按段了,不断反复进行下去,对处于当中的大部分数据源,其工作效率要高一些所以尽管斐波那契查找的时间复杂度也为O(logn)。但品均性能上来说,斐波那契查找要优于折半查找,可惜如果是最坏情况,比如这里key=1的时候,那么始终都处于左侧长半区在查找,则查找效率要低于折半查找。

还有一点比较关键,折半查找是进行假发与除法运算(mid={low+high}/2),插值查找进行复杂的四则运算(mid=low+(high-low)*(key-a[low])/(a[high]-a[low])),而斐波那契额查找只是最简单加减运算(mid=low+F[k-1]-1),在海量数据的查找过程中,这种细微的差别可能会影响最终的查找效率。

应该说“顺序表查找”、“折半查找”、“插值查找”这三种查找本质上是分隔点不同,各有优劣,实际开发过程中可根据实际情况中数据的综合特点再做出选择。

#include<stdio.h>

int F[] = {0,1,1,2,3,5,8,13,21,34,55};

int Binary_Search(int *a,int n,int key){

int low,mid,high,i,k;

low = 1;

high = n; 

k = 0;

while(n>F[k]-1)

k++; 

for(i=n;i<F[k]-1;i++)

a[i]=a[n];

while(low<=high){

mid=low+F[k-1]-1;

if(key<a[mid]){

high=mid-1;

k--;

}

else if(key>a[mid]){

low=mid+1;

k=k-2;

}

else{

if(mid<=n)

return mid;

else

return n;

}

}

return 0;

}

void main(){

int num[] = {0,1,26,24,35,47,59,62,73,88,99};

int result = Binary_Search(num,sizeof(num)/sizeof(num[0])-1,62);

printf("'斐波那契查找'结果为:%d/n",result);

}

数据结构之斐波那契查找

正文到此结束
Loading...