写点什么

斐波那契查找

用户头像
ilovealt
关注
发布于: 2020 年 11 月 21 日

有序查找(折半查找、插值查找、斐波那契查找)的三个方法都是按照一定的分割比例进行查找,折半查找是对半分割,插值查找是靠近分割,斐波那契查找是黄金分割。

斐波那契数列

斐波那契数列(Fibonacci sequence):又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(≥ 2,∈ N*)。

黄金分割:黄金分割是指将整体一分为二,较大部分与整体部分的比值等于较小部分与较大部分的比值,其比值约为 0.618。这个比例被公认为是最能引起美感的比例,因此被称为黄金分割。

算法核心

算法要求数据个数: n=F[k]-1, 分割点:mid=low+F[k-1]-1.

查找的数据 key,和数组 mid 位置的数据对比结果如下:

  1. 相等,查找成功;

  2. 小于,则 high = mid-1,k-=1;

说明:如图所示,high = mid-1 说明 key 的值可能在[low,mid-1]之间,k-=1 说明在[low,mid-1]之间有 F[k-1]-1 个元素;

  1. 大于,则 low = mid+1,k-=2;

说明:如图所示,low = mid+1 说明 key 的值可能在[mid+1,high]之间,k-=2 说明在[mid+1,high]之间有 F[k-2]-1 个元素;

关于 F[k]-1:由斐波那契数列的公式可知,F[k]=F[k-1]+F[k-2],那么 F[k]-1=(F[k-1]-1)+(F[k-2]-1)+1,所以数组长度只需要满足 F[k]-1,就可以把数组分为 F[k-1]-1 和 F[k-2]-1 左右两部分,mid=low+F[k-1]-1。

代码

C 语言实现:

#include <stdio.h>#include <math.h>
#define MAXSIZE 50 /*存储空间初始分配量*/

int F[50]; /*斐波那契数列*/

/*斐波那契查找*/int Fibonacci_Search(int *a, int n, int key){ int low,high,mid,i,k = 0; low = 1; high = n; 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 = k - 1; } else if (key > a[mid]) { low = mid + 1; k = k - 2; } else { if(mid <= n) return mid; else return n; } } return 0;}
int main() { int result; int arr[MAXSIZE]={0,1,16,24,35,47,59,62,73,88,99};
//斐波那契 int i; F[0] = 0; F[1] = 1; for (i = 2; i < MAXSIZE; i++) { F[i] = F[i-1] + F[i-2]; } result = Fibonacci_Search(arr, 10, 62); printf("Fibonacci_Search:%d \n", result);
return 0;}
复制代码

对比

斐波那契查找的时间复杂度为 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),在海量数据的查找过程中,这种细微差别可能会影响最终的查询效率。

注意: 折半查找计算 mid 为了放值溢出,推荐使用(mid=low+(high-low)/2)。


成长快乐,成长快乐,成长快乐


参考:

《大话数据结构》

查找--斐波那契查找

七大查找算法

发布于: 2020 年 11 月 21 日阅读数: 50
用户头像

ilovealt

关注

不忘初心,方得始终! 2018.05.02 加入

When you feel like giving up,remember why you held on so long in the first place.

评论

发布
暂无评论
斐波那契查找