1.查找算法概述
查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。
（1）查找定义
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
（2）查找算法分类
1）静态查找和动态查找
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。
（3）查找算法分析
平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。
Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。
2.斐波那契查找
（1）斐波那契查找说明
在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。
黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。
0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。
大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。
（2）基本思想
也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;
斐波那契查找的核心是：
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]范围内查找。
（3）复杂度分析
最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。
网上都没有讲清楚，导致外行很难直接直观的理解斐波那契查找。
我认为，斐波那契的核心在于两点：
1）斐波那契是一种特殊的分割方法，和二分、插值本质上是一样的，都是分割方法；
2）利用了斐波那契数列特殊的性质，一个长度只要可以被黄金分割，那么分割后的片段仍然可以继续进行黄金分割，循环。
首先，我们构造一个完整的斐波那契数列，然后开始分，小于就取左边的分割，F变为F-1；大于就取右边的分割，F变为F-2。
很好理解，F-1 和 F-2，自己画个图就理解了，这是菲波那切数列特殊的性质。
（4）斐波那契查找算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <stdio.h> #include <stdlib.h> #define MAXN 20 //产生斐波那契数列 void Fibonacci(int *f) { int i; f[0] = 1; f[1] = 1; for (i = 2; i < MAXN; ++i) f[i] = f[i - 2] + f[i - 1]; } // 查找--有序查找 int Fibonacci_Search(int *a, int key, int n) { int i, low = 0, high = n - 1; int mid = 0; int k = 0; int F[MAXN]; Fibonacci(F); while (n > F[k] - 1) //计算出n在斐波那契中的数列 ++k; for (i = n; i < F[k] - 1; ++i) //把数组补全 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 0; } int main() { int a[MAXN] = { 5, 15, 19, 20, 25, 31, 38, 41, 45, 49, 52, 55, 57 }; int k, res = 0; printf("请输入要查找的数字:\n"); scanf("%d", &k); res = Fibonacci_Search(a, k, 13); if (res != -1) printf("在数组的第%d个位置找到元素:%d\n", res + 1, k); else printf("未在数组中找到元素:%d\n", k); return 0; } |
（5）斐波那契查找算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ /*斐波那契查找法，前提是线性表必须有序,时间复杂度是O(logn)*/ #include<iostream> const int MAXSIZE = 20; /*定义斐波那契查找法*/ int Fibonacci_Search(int *a, int n, int key) { int low, high, mid, i, k; int F[MAXSIZE]; Fibonacci(F); //构造一个斐波那契数组F low = 1; //最低下标记录为首位 high = n; //最高下标记录为末位 k = 0; while(n > F[k]-1) //计算n位于斐波那契数列的位置 { k++; } for(i=n; i<F[k]-1; i++) //将a的元素扩展到(某斐波那契数 - 1)，即F[k]-1 { a[i] = a[n]; } while(low <= high) { mid = low + F[k-1] - 1; //计算当前分割的下标 if(key < a[mid]) { high = mid - 1; k -= 1; } else if(key > a[mid]) { low = mid + 1; k -= 2; } else { if(mid <= n) return mid; //若相当则说明mid即为查找到的位置 else return n; //若mid>n则说明是扩展的数值，返回n } } return -1; } /*用非递归法构造一个斐波那契数组*/ void Fibonacci(int *f) { f[0] = 1; f[1] = 1; for(int i=2; i<MAXSIZE; i++) { f[i] = f[i-1] + f[i-2]; } } int main() { int array[] = {0,16,24,35,47,59,62,73,88,99}; int number = Fibonacci_Search(array, sizeof(array)/sizeof(int), 73); std::cout<<"位置是：array["<<number<<"]\n"; return 0; } |
