赞
踩
斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术。斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。(mid的关系式不同)
斐波那契查找同样是查找算法家族中的一员,它要求数据是有序的(升序或降序)。斐波那契查找采用和二分查找/插值查找相似的区间分割策略,都是通过不断的分割区间缩小搜索的范围 。(分治法)
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为 “兔子数列”。
如下图所示,就是一个斐波那契数列:
在数学上,斐波那契数列被以如下递推的方法定义:
F
(
0
)
=
0
,
F
(
1
)
=
1
F ( 0 ) = 0 , F ( 1 ) = 1
F(0)=0,F(1)=1
F
(
n
)
=
F
(
n
−
1
)
+
F
(
n
−
2
)
(
n
≥
2
,
n
∈
N
∗
)
F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n ≥ 2 , n ∈ N ∗ )
F(n)=F(n−1)+F(n−2)(n≥2,n∈N∗)
从斐波那契的递推公式我们可以总结出重要一点:斐波那契数列从第三项开始,每一项都等于前两项之和。
如上图所示:
F[k]-1
是待搜索的数组中数组的长度,之所以使F[k]-1
为数组的长度目的是满足以下关系式:
F
(
n
)
−
1
=
F
(
n
−
1
)
−
1
+
F
(
n
−
2
)
−
1
(
n
≥
2
,
n
∈
N
∗
)
F ( n )-1 = F ( n − 1 )-1 + F ( n − 2 )-1 ( n ≥ 2 , n ∈ N ∗ )
F(n)−1=F(n−1)−1+F(n−2)−1(n≥2,n∈N∗)
以实现mid将一个数组分为两个数组
正是上面这样的区间分割想法,使斐波那契数列和数组联系到了一起。这种分割思想亦是斐波那契查找算法的基础。
斐波那契查找算法相对于二分查找和插值查找的基本思路是一致的,其中最重要的区别就是它们的查找点(或称中间值)的确定。斐波那契查找算法的查找点的计算公式如下:
m
i
d
=
l
e
f
t
+
F
(
n
−
1
)
−
1
mid=left+F(n−1)−1
mid=left+F(n−1)−1
所以,斐波那契查找和二分查找或插值查找没有本质的区别,都是对待搜索的数组进行分割,分割的边界就是mid的值。只不过mid值生成方程式不同。
从上面我们知道了斐波那契查找算法的基本思想,根据它的基本思想,斐波那契查找的基本步骤可以分为以下几步:
/*构造一个斐波那契数组*/ void Fibonacci(int* F) { F[0] = 0; F[1] = 1; for (int i = 2; i < MAX_SIZE; ++i) F[i] = F[i - 1] + F[i - 2]; } /*定义斐波那契查找法*/ int FibonacciSearch(int* a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字 { int low = 0; int high = n - 1; int k = 0; int F[MAX_SIZE] = {0}; Fibonacci(F);//构造一个斐波那契数组F while (n > F[k] - 1)//计算n位于斐波那契数列的位置 ++k; int* temp;//将数组a扩展到F[k]-1的长度 temp = malloc(sizeof(int)*(F[k]-1)); memcpy(temp, a, n * sizeof(int));//将a中的元素进行拷贝至temp for (int i = n; i < F[k] - 1; ++i)//填充数组 temp[i] = a[n - 1]; while (low <= high)//终止条件和二分查找一致 { int mid = low + F[k - 1] - 1;//递推关系式,获取mid值 if (key < temp[mid]) { high = mid - 1; k -= 1; } else if (key > temp[mid]) { low = mid + 1; k -= 2; } else { free(temp);//记得free if (mid < n) return mid; //若相等则说明mid即为查找到的位置 else return n - 1; //若mid>=n则说明是扩展的数值,返回n-1 } } free(temp);//记得free return -1; }
#define MAX_SIZE 20
void main()
{
int a[] = {0,16,24,35,47,59,62,73,88,99};//待搜索的数组
int key = 59;//在数组中的位置为5
int index = FibonacciSearch(a, sizeof(a) / sizeof(int), key);
printf("FibonacciSearch positino %d\n", index);
system("pause");
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。