斐波那契搜索优化版

1 简介

• 该算法是对二分法的改进。
• 处理的数组是已经排序过的数组。
• 斐波那契数列 int a[] = {1,1,2,3,5,8,13,21,34,55,89……}
  • 相邻的两个数越大，比例越接近黄金比例 0.618:1
• 可以观察到 a[i] = a[i-1] + a[i-2]
  • 根据这个特点，每次以 a[i-1] 为分界线划分原数组，mid = arr[a[i-1]] 。
  • 如果 mid 比要查找的数大，则 i = i-1。如果 mid 比要查找的数小，则 i = i-2
• 优点：
  • 时间复杂度为 log2n ，与二分法旗鼓相当。
  • 只使用了加减法进行运算，不使用乘除法。所以在运算效率上相比于二分查找和插值查找更有优势，当然也得看情况而论。

我根据网上给出的算法进行了小改进，因为我发现以下2个问题：

1. 在查找与原数组长度最接近的最大斐波那契数时，使用了 F[k]-1 这个数来找到在斐波那契数列中最接近的数组长度的最大数列值，解释说是为了方便后续编程。但我把这个给改了，因为按照正常人的思路 F[k] 才是最先想到的，并且使用 F[k] 后，并不会使得编程添加太多代码。。。
2. 网上给出的代码，在构造斐波那契数组的时候，以给定的最大长度来构造的。但是我觉得，这样做没必要，只需要构建到满足需求就可以了啊。

2 代码

#include <stdio.h>
#include <iostream>
using namespace std;

// 数组最大长度
#define MAXSIZE 20
// 数组长度
#define ARR_LEN 13

/// <summary>
/// 构造斐波那契数列
/// </summary>
/// <param name="f">斐波那契数组</param>
/// <param name="n">原数组的长度</param>
void fibonacci(int* f,int n)
{
	int i=2;
	f[0] = 1;
	f[1] = 1;
	while (f[i-1] <= n)
	{
		f[i] = f[i - 2] + f[i - 1];
		i++;
	}
}
/// <summary>
/// 斐波那契查找算法
/// </summary>
/// <param name="a">待查找的数组</param>
/// <param name="key">待查找的数据</param>
/// <param name="n">数组长度</param>
/// <returns>所在的索引</returns>
int fibonacci_search(int* a, int key, int n)
{
	int low = 0;
	int high = n - 1;
	int mid = 0;
	int k = 0;
	int F[MAXSIZE];
	int i;
	// 防止错误的长度
	if (n <= 0) return-1;
	// 限制上下限
	if (key<a[0] || key>a[n - 1]) return -1;
	// 如果数组长度为1，则直接判断
	if (n == 1) return key == a[0] ? 0 : -1;
	// 构造斐波那契数组
	fibonacci(F,n);
	// 找到有序表元素个数在斐波那契数列中最接近的最大数列值
	while (n > F[k]) ++k;
	// 将原数组的长度和找到的斐波那契数列值对齐
	// 用最大值补齐
	for (i = n; i < F[k]; ++i)
	{
		a[i] = a[high];
	}
	while (low <= high)
	{
		// 根据斐波那契数列得到分割位置
		if (k != 1) mid = low + F[k - 1];
		else mid = low + 0;
		if (a[mid] > key)
		{
			// 如果分隔值大了
			high = mid - 1;
			// 斐波那契数列的索引后退一格
			k = k - 1;
		}
		else if (a[mid] < key)
		{
			// 如果分隔值小了
			low = mid + 1;
			// 斐波那契数列的索引后退两格
			k = k - 2;
		}
		else
		{
			// 如果找到了，要判断是否是到增补的部分
			return mid <= high ? mid : high;
		}
	}
	return -1;
}

int main()
{
	// 数组的长度一定要够用
	// 使用的时候，会把数组长度和斐波那契数组的数对齐。
	int a[MAXSIZE] = { 1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88 };
	int key;
	int pos;
	// 打印数组
	cout << "{";     
	for (int i = 0;i < ARR_LEN;i++) {
		cout << a[i];         
		if (i < ARR_LEN -1)cout << ",";
	}     
	cout << "}" << endl;
	while (1)
	{
		printf("请输入要查找的数字:");
		scanf_s("%d", &key);
		pos = fibonacci_search(a, key, ARR_LEN);

		if (pos != -1)
		{
			printf("\n查找成功，可喜可贺，可口可乐! 关键字 %d 所在的位置是: %d\n\n", key, pos);
		}
		else
		{
			printf("\nO~No~~小的办事不力，未在数组中找到元素:%d\n\n", key);
		}
	}
	return 0;
}