在介紹斐波那契查找之前我們要先了解兩件事，黃金分割和斐波那契數(shù)列，二者是啥關(guān)系。

首先是黃金分割（也叫黃金比例），這個(gè)詞經(jīng)常出現(xiàn)在一些建筑物的設(shè)計(jì)，黃金分割的近似值是0.618。斐波那契數(shù)列又稱黃金比例數(shù)列，指的是這樣的數(shù)列：1、1、2、3、5、8、13、21、34……，這個(gè)數(shù)列從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和（F[K] = F[K-1] + F[K-2]）；隨著斐波那契數(shù)列的遞增，前后兩個(gè)數(shù)的比值會(huì)越來越接近0.618，利用這個(gè)特性，我們就可以把黃金比例運(yùn)用到查找當(dāng)中。

斐波那契查找依舊基于數(shù)組是有序數(shù)組，并使數(shù)組長(zhǎng)度與斐波那契數(shù)組元素相匹配，之后類似于二分查找。

斐波那契查找總共分為以下幾步：

1.構(gòu)建斐波那契數(shù)列

2.計(jì)算數(shù)組長(zhǎng)度對(duì)應(yīng)的斐波那契數(shù)列元素個(gè)數(shù)

3.對(duì)數(shù)組進(jìn)行填充

4.循環(huán)進(jìn)行區(qū)間分割，查找中間值

5.判斷中間值和目標(biāo)值的關(guān)系，確定更新策略

首先構(gòu)建斐波那契數(shù)列

計(jì)算數(shù)組長(zhǎng)度對(duì)應(yīng)的斐波那契數(shù)列元素個(gè)數(shù)

假設(shè)手中的數(shù)據(jù)如下：

目前數(shù)組中的15個(gè)元素均不對(duì)應(yīng)斐波那契數(shù)列中的F[n]，這種情況就使用策略“大于數(shù)組長(zhǎng)度的最近一個(gè)斐波那契數(shù)值”，當(dāng)前數(shù)組的最大值是18，斐波那契數(shù)列中大于18的最近元素為21。

對(duì)數(shù)組進(jìn)行填充

確定了斐波那契數(shù)值之后，將數(shù)組第18位到21位進(jìn)行填充，使用最大值進(jìn)行填充，即18位到21位均為18。

循環(huán)進(jìn)行區(qū)間分割，查找中間值

這一步和二分查找很相似，都是不斷縮小范圍查找中間值Mid，斐波那契查找中mid的公式如下：

Low + F[K-1]-1

中間值和目標(biāo)值的關(guān)系分為三種

1)相等

數(shù)列中存在目標(biāo)值；

2)目標(biāo)值大于中間值

新的查找范圍在mid+1到第high個(gè)，此時(shí)范圍個(gè)數(shù)為F[K-2]-1個(gè)，即數(shù)組右邊的長(zhǎng)度，所以要在[low,F[k-2]-1]范圍查找；

3)目標(biāo)值小于中間值

重新確定查找范圍，新的查找范圍是第low個(gè)到第mid-1個(gè)，此時(shí)范圍個(gè)數(shù)為F[K-1]-1個(gè)，即數(shù)組左邊的長(zhǎng)度，所以要在[low,F[k-1]-1]范圍查找；

#include<stdio.h>

#define MAXSIZE 20

void fibonacci(int *f)? ? //構(gòu)建斐波那契序列

{

? ? 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) //計(jì)算出n在斐波那契中的位置

{

? ?++k;

}

? ? for(int i = n; i < F[k] - 1; ++i) //把數(shù)組補(bǔ)全，使用a[n-1]

? ? ? ? a[i] = a[high];

? ? while(low <= high){

? ? ? ? mid = low + F[k-1] - 1;? //根據(jù)斐波那契數(shù)列進(jìn)行黃金分割

? ? ? ? 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) //如果為真則找到相應(yīng)的位置

? ? ? ? ? ? ? ? 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 = 9;

? ? int pos = fibonacci_search(a,k,13);

? ? if(pos != -1)

? ? ? ? printf("在數(shù)組的第%d個(gè)位置找到元素:%d\n",pos + 1,k);

? ? else

? ? ? ? printf("未在數(shù)組中找到元素:%d\n",k);

? ? return 0;

}

文章來源：學(xué)到牛牛 www.xuedaon.com