查找算法：斐波那契查找算法实现及分析

港控/mmm° 2022-05-29 23:11 247阅读 0赞

# 斐波那契查找算法介绍 #

**斐波那契查找法肯定与斐波那契相关嘛，斐波那契数列 又称黄金分割数列**。所以我们**先把黄金分割弄懂，后面代码才能看得懂**！黄金分割点大家都知道吧。**1:0.618或者1.618:1**，我们的斐波那契数列越往后的项数 越接近黄金分割比例，打个比方

斐波那契数列第k项 **F\[k\] = F\[k-1\]+F\[k-2\]。F\[k-1\] : F\[k-2\] ≈ 1:0.618** 。回忆下我们的折半查找mid = （low+high）/2取中间的位置，我们的插值查找呢 mid = （low+high）\*（key-arr\[low\]）/（arr\[high\]-arr\[low\]）根据key值的一个占比来确定mid的位置。那么我们的斐波那契查找呢，就是采用斐波那契数列来确定 **mid的位置！mid = low + F\[k-1\] - 1**；看下图：

![20180227231737968][]

# 斐波那契算法代码实现 #

代码和折半查找很相似，**计算mid的公式变为mid = low + F\[k-1\] - 1**；然后就是将目标数组数据扩充至F\[k\]-1个，扩充元素值为最值。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    
    void PrintArr(int* arr,int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		printf("%3d ",arr[i]);
    	}
    	printf("\n");
    	return;
    }
    
    //构造斐波那契数列
    int* Fibonacci_Arr(int length)
    {
    	int* arr = malloc(sizeof(int)*length);
    	arr[0] = 0;
    	arr[1] = 1;
    	for (int i = 2; i < length; i++)
    	{
    		arr[i] = arr[i - 1] + arr[i - 2];
    	}
    	return arr;
    }
    
    //斐波那契查找法 
    //arr 数组，下标为[0,length-1]，length 数组长度，key 查找的关键字
    //返回查找值的下标 ，没查找到 返回-1
    int Fibonacci_Search(int *arr,int* F, int length, int key)
    {
    	int low = 0;		//低位下标
    	int high = length-1;//高位下标
    	int mid;			//中间值下标
    	int k = 0;			//斐波那契数列下标
    	//计算arr的length 位于斐波那契数列的位置
    	while (length > F[k] - 1)
    	{
    		k++;
    	}
    	//arr数组长度不满足斐波那契数据项长度 将后面的值填充为最大值
    	for (int i = length; i < F[k]-1; i++)
    	{
    		arr[i] = arr[high];
    	}
    
    	while (low <= high)
    	{
    		mid = low + F[k - 1] - 1;//将mid的值设置为黄金分割点位置
    		if (key < arr[mid])
    		{
    			high = mid - 1;
    			k = k - 1;
    		}
    		else if(key > arr[mid])
    		{
    			low = mid + 1;
    			k = k - 2;
    		}
    		else
    		{
    			if (mid <= length - 1)
    			{
    				return mid;
    			}
    			else
    			{
    				return length - 1;
    			}
    		}
    	}
    	return -1;
    }
    int main(int argc, char *argv[])
    {
    	int arr[15] = { 0,1,2,13,24,35,46,57,68,99};//10个元素，空几个位置预留用
    	int length = 10;
    	//构造斐波那契数列
    	int *F = Fibonacci_Arr(length);
    	printf("斐波那契数列:");
    	PrintArr(F, length);
    	printf("目标数组    :");
    	PrintArr(arr, 10);
    	//斐波那契查找
    	int key = 46;
    	int index = Fibonacci_Search(arr, F, length, key);
    	printf("%d的下标index = %d\n", key, index);
    	key = 56;
    	index = Fibonacci_Search(arr, F, length, key);
    	printf("%d的下标index = %d\n", key, index);
    
    	return 0;
    }

# 代码运行检测 #

![20180227233008205][]

[20180227231737968]: /images/20220530/1f86fbbe43424d2d844b3a26a65b3579.png
[20180227233008205]: /images/20220530/ecb98c63cdc64972aa5512e240047a09.png