斐波那契查找的核心是:
1)当key=a[mid]时,查找成功;
2)当key<a[mid]时,新的查找范围是第low个到第mid-1个,此时范围个数为F[k-1] - 1个,即数组左边的长度,所以要在[low, F[k - 1] - 1]范围内查找;
3)当key>a[mid]时,新的查找范围是第mid+1个到第high个,此时范围个数为F[k-2] - 1个,即数组右边的长度,所以要在[F[k - 2] - 1]范围内查找。
#include<stdio.h> #include<string.h> #include<math.h> #include<ctype.h> #include<stdbool.h> #define MAXSIZE 20 void fibonacci(int *f) //构建斐波那契序列 { f[0] = 1; f[1] = 1; for(int i = 2; i < MAXSIZE; ++i) f[i] = f[i - 2] + f[i - 1]; } int fibonacci_search(int *a,int key,int n) { int low = 0,high = n - 1; int mid = 0; int k = 0; int F[MAXSIZE]; fibonacci(F); while(n > F[k] - 1) //计算出n在斐波那契中的位置 ++k; for(int i = n; i < F[k] - 1; ++i) //把数组补全,使用a[n-1] a[i] = a[high]; while(low <= high){ mid = low + F[k-1] - 1; //根据斐波那契数列进行黄金分割 if(a[mid] > key){ high = mid - 1; k = k - 1; } else if(a[mid] < key){ low = mid + 1; k = k - 2; } else{ if(mid <= high) //如果为真则找到相应的位置 return mid; else return -1; } } return -1; } int main() { int a[MAXSIZE] = {5,15,19,20,25,31,38,41,45,49,52,55,57}; int k; printf("请输入要查找的数字:\n"); scanf("%d",&k); int pos = fibonacci_search(a,k,13); if(pos != -1) printf("在数组的第%d个位置找到元素:%d\n",pos + 1,k); else printf("未在数组中找到元素:%d\n",k); return 0; }
相关推荐
二分查找,O(logn)的经典查找算法,实现在一个非下降序列中快速查找一个值是否存在。 插值查找是对二分查找的一个扩展,对于接近线性递增的序列效率极高,其他情况效率一般。 斐波那契查找,纯娱乐用的东西,存在...
掌握不同的检索方法,并能用高级语言实现检索算法; 熟练掌握顺序表和有序表的检索方法,以及静态检索树的构造方法和检索算法,理解静态检索树的折半检索方法; 熟练掌握二叉排序树的构造和检索方法; ...
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数...查找算法包括:线性查找、二分查找、插值查询、斐波那契(黄金分割法)、
所谓查找(Search)又称检索,就是在一个数据...查找算法的效率高低直接关系到应用系统的性能。本次实验是在折半查找的代码基础上,实现插值查找和斐波那契查找,并比较不同的数据这三种方法的查找效率,得出初步结论。
C++二分查找、插值查找、斐波那契查找对比C++的实现源码,不是完整程序,仅是核心算法文件 想要跑起来 自己要懂得动动手咯
在计算机科学领域,斐波那契数列常用于算法设计,如斐波那契查找算法,其时间复杂度为O(log n),比普通的二分查找算法更高效。在数学领域,斐波那契数列被用于解决数列求和问题以及递归算法的问题。在自然科学领域,...
查找算法 线性查找二分查找差值查找斐波那契查找 鉴于在排序算法时, 搞得比较乱的情况, 导致查找不太方便. 因此, 在写查找算法时, 我会将所有的东西都写在一起, 便于查找和阅读 在java中,我们常用的查找有四种: ...
算法-理论基础- 查找- 斐波那契查找(包含源程序).rar
搜索算法:搜索算法用于在数据集中查找特定元素的算法。常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法...
用C++写的Fibonacci 查找算法的实现,可以稍作修改当成标准的C程序用。
02-D2-7 查找长度 & Fibonacci查找1
1. 顺序查找 2. 二分查找[2] 3. 插值查找 4. 斐波那契查找 5. 树表查找 6. 分块查找 7. 哈希查找
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫...斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和...
##查找算法 二分查找算法 第k小数选择算法 随机第k小数选择算法 计算集合中两个元素的和和一个数相等 ##动态规划 使用分治法的最大子数组(应该算成分治法) 使用自底向上方法实现的最大子数组 使用动态规划的两种...
│ ├── Fibonacci.php 斐波那契数列 │ ├── StealingApples.php 偷苹果求余 │ ├── HanoiGames.php 汉诺塔游戏 │ ├── BidirectionalQueue.php 双向队列 │ ├── ColorBricks....
数据结构与算法的一些实例,数据结构包括图(遍历算法)、树(哈夫曼树、AVL平衡树等),算法包括查找算法(二分查找、斐波那契查找等)、排序算法(快速排序、堆排序等)、贪心算法、KMP算法等.zip
(4)斐波那契查找 (Search_Fib) (5)次优查找树(BiTree_SOSTree) 11. 动态查找 (1)在二叉排序树上进行查找(bstsrch)、插入结点(ins_bstree)和删除结点(del_bstree) (2)在二叉平衡树上插入结点(ins_AVL...
运用斐波拉契算法进行数据查询,运行后根据提示输入要查找的数据