費(fèi)氏搜尋法簡介

費(fèi)氏搜尋法，就是利用斐波那契數(shù)列從有序數(shù)列中搜尋特定元素的一種搜索算法。

二分搜尋法每次搜尋時，都會將搜尋區(qū)間分為一半，所以其搜尋時間為O(log(2)n)，log(2)表示以2為底的log值，這邊要介紹的費(fèi)氏搜尋，其利用費(fèi)氏數(shù)列作為間隔來搜尋下一個數(shù)，所以區(qū)間收斂的速度更快，搜尋時間為O(logn)。

費(fèi)氏搜尋法算法分析

費(fèi)氏搜尋使用費(fèi)氏數(shù)列來決定下一個數(shù)的搜尋位置，所以必須先制作費(fèi)氏數(shù)列，這在之前有提過；費(fèi)氏搜尋會先透過公式計算求出第一個要搜尋數(shù)的位置，以及其代 表的費(fèi)氏數(shù)，以搜尋對象10個數(shù)字來說，第一個費(fèi)氏數(shù)經(jīng)計算后一定是F5，而第一個要搜尋的位置有兩個可能，例如若在下面的數(shù)列搜尋的話（為了計算方便， 通常會將索引0訂作無限小的數(shù)，而數(shù)列由索引1開始）：

-infin; 1 3 5 7 9 13 15 17 19 20

如果要搜尋5的話，則由索引F5 = 5開始搜尋，接下來如果數(shù)列中的數(shù)小于指定搜尋值時，就往左找，大于時就向右，每次找的間隔是F4、F3、F2來尋找，當(dāng)費(fèi)氏數(shù)為0時還沒找到，就表示尋找失敗，如下所示：

?

由于第一個搜尋值索引F5 = 5處的值小于19，所以此時必須對齊數(shù)列右方，也就是將第一個搜尋值的索引改為F5+2 = 7，然后如同上述的方式進(jìn)行搜尋，如下所示：

至于第一個搜尋值是如何找到的？我們可以由以下這個公式來求得，其中n為搜尋對象的個數(shù)：

F_x?+ m = n

F_x?<= n

也就是說Fx必須找到不大于n的費(fèi)氏數(shù)，以10個搜尋對象來說：

F_x?+ m = 10

取F_x?= 8, m = 2，所以我們可以對照費(fèi)氏數(shù)列得x = 6，然而第一個數(shù)的可能位置之一并不是F6，而是第x-1的費(fèi)氏數(shù)，也就是F₅?= 5。

如果數(shù)列number在索引5處的值小于指定的搜尋值，則第一個搜尋位置就是索引5的位置，如果大于指定的搜尋值，則第一個搜尋位置必須加上m，也就是F₅?+ m = 5 + 2 = 7，也就是索引7的位置，其實(shí)加上m的原因，是為了要讓下一個搜尋值剛好是數(shù)列的最后一個位置。

費(fèi)氏搜尋看來難懂，但只要掌握F_x?+ m = n這個公式，自己找?guī)讉€實(shí)例算一次，很容易就可以理解；費(fèi)氏搜尋除了收斂快速之外，由于其本身只會使用到加法與減法，在運(yùn)算上也可以加快。

費(fèi)氏搜尋法的實(shí)現(xiàn)

#define MAX 15 #define SWAP(x,y) {int t; t = x; x = y; y = t;}void createfib(void); // 建立費(fèi)氏數(shù)列 int findx(int); // 找x值 int fibsearch(int[], int); // 費(fèi)氏搜尋 void quicksort(int[], int, int); // 快速排序int Fib[MAX] = {-999};

?

//主程序（C/OC） int number[MAX] = {0}; int i, find;srand(time(NULL));for(i = 1; i <= MAX; i++) { //產(chǎn)生隨機(jī)數(shù)列number[i] = rand() % 10; }quicksort(number, 1, MAX); //快速排序printf("數(shù)列："); //打印排序后的數(shù)列 for(i = 1; i <= MAX; i++)printf("%d ", number[i]); find = 6; //要尋找的對象 if((i = fibsearch(number, find)) >= 0)printf("找到數(shù)字于索引 %d ", i); elseprintf("\n找不到指定數(shù)");printf("\n");

?

//建立費(fèi)氏數(shù)列，總共求得MAX+1個斐波那契數(shù) void createfib(void) {int i;Fib[0] = 0;Fib[1] = 1;for(i = 2; i < MAX; i++)Fib[i] = Fib[i-1] + Fib[i-2]; }//找x值 int findx(int n) {int i = 0;while(Fib[i] <= n)i++;i--;return i;//找到第i個Fib元素小于等于MAX+1 }//費(fèi)式搜尋 int fibsearch(int number[], int find) {int i, x, m;createfib(); //創(chuàng)建斐波那契數(shù)列x = findx(MAX+1); //斐波那契數(shù)列中第x個數(shù)剛好不大于MAX+1。MAX是確定的，所以比較的起始點(diǎn)是確定的。m = MAX - Fib[x]; //得到一個較小的差值。m的值也是確定的。printf("\nx = %d, m = %d, Fib[x] = %d\n\n",x, m, Fib[x]);x--;i = x;if(number[i] < find) //i的初值也是確定的。PS：這就是公式的力量i += m;while(Fib[x] > 0) { //搜尋，x值不斷減小，范圍越來越小，搜尋越來越精細(xì)if(number[i] < find) //小于被搜尋的值i += Fib[--x]; //右移搜尋位置else if(number[i] > find) //大于被搜尋值i -= Fib[--x]; //左移搜尋位置elsereturn i; //相等，找到}return -1; //搜尋步子已經(jīng)最小，還是沒找到，搜尋結(jié)束 }//快速排序 void quicksort(int number[], int left, int right) {int i, j, k, s;if(left < right) {s = number[(left+right)/2];i = left - 1;j = right + 1;while(1) {while(number[++i] < s) ; // 向右找while(number[--j] > s) ; // 向左找if(i >= j)break;SWAP(number[i], number[j]);}quicksort(number, left, i-1); // 對左邊進(jìn)行遞回quicksort(number, j+1, right); // 對右邊進(jìn)行遞回} }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/riasky/p/3508807.html

總結(jié)

以上是生活随笔為你收集整理的费氏搜寻法之算法分析与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。