斐波那契搜索(Fibonacci search),又稱斐波那契查找,是區(qū)間中單峰函數(shù)的搜索技術。

斐波那契搜索就是在二分查找的基礎上根據(jù)斐波那契數(shù)列進行分割的。在斐波那契數(shù)列找一個等于略大于查找表中元素個數(shù)的數(shù)F[n],將原查找表擴展為長度為F[n](如果要補充元素,則補充重復最后一個元素,直到滿足F[n]個元素),完成后進行斐波那契分割,即F[n]個元素分割為前半部分F[n-1]個元素,后半部分F[n-2]個元素,找出要查找的元素在那一部分并遞歸,直到找到。

外文名

Fibonacci search

別名

斐波那契查找

領域

數(shù)學、計算機

屬性

區(qū)間搜索技術

對象

單峰函數(shù)

引言

斐波那契搜索

在介紹斐波那契查找算法之前,先介紹一下很它緊密相連的一個概念——黃金分割。黃金比例又稱黃金分割,是指事物各部分間一定的數(shù)學比例關系,即將整體一分為二,較大部分與較小部分之比等于整體與較大部分之比,其比值約為

。0.618被公認為最具有審美意義的比例數(shù)字,這個數(shù)值的作用不僅僅體現(xiàn)在諸如繪畫、雕塑、音樂、建筑等藝術領域,而且在管理、工程設計等方面也有著不可忽視的作用。因此被稱為黃金分割。斐波那契數(shù)列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….(從第三個數(shù)開始,后邊每一個數(shù)都是前兩個數(shù)的和)。然后我們會發(fā)現(xiàn),隨著斐波那契數(shù)列的遞增,前后兩個數(shù)的比值會越來越接近0.618,利用這個特性,我們就可以將黃金比例運用到查找技術中。

相對于折半查找,一般將待比較的key值與第

位置的元素比較,比較結果分三種情況:

(1)key值與第

相等,mid位置的元素即為所求;

(2)key值大于第

,則令

(3)key值小于第

,則令

。

斐波那契搜索也是二分查找的一種提升算法,通過運用黃金比例的概念在數(shù)列中選擇查找點進行查找,提高查找效率。同樣地,斐波那契查找也屬于一種有序查找算法。

簡介

斐波那契查找與折半查找很相似,他是根據(jù)斐波那契序列的特點對有序表進行分割的。他要求開始表中記錄的個數(shù)為某個斐波那契數(shù)小1,及

;開始將k值與第

位置的記錄進行比較(及

,比較結果也分為三種:

(1)相等,則mid位置的元素即為所求;

(2)>,則

;

說明:

說明待查找的元素在

范圍內,

說明范圍

內的元素個數(shù)為

個,所以可以遞歸的應用斐波那契查找。

(3))<,則

,

說明:

說明待查找的元素在

范圍內,

說明范圍

內的元素個數(shù)為

個,所以可以遞歸的應用斐波那契查找。

在最壞情況下,斐波那契查找的時間復雜度還是

,且其期望復雜度也為

,但是與折半查找相比,斐波那契查找的優(yōu)點是它只涉及加法和減法運算,而不用除法,而除法比加減法要占用更多的時間,因此,斐波那契查找的運行時間理論上比折半查找小,但是還是得視具體情況而定。

斐波那契搜索原理

斐波那契搜索是一種有限區(qū)間中單峰函數(shù)的搜索技術。為簡單起見,設此區(qū)間為

,記

為斐波那契數(shù),

,第一次估值點為:

,其中,

應等于或小于搜索的預期精度。若

,則刪去

,反之刪去

。以

記刪去的區(qū)間,再對留下的區(qū)間

取:

,其中,

的長度。對L重復上述步驟。如此反復直到:

已經(jīng)證明,斐波那契搜索是一種函數(shù)估值次數(shù)最少的最優(yōu)搜索方法。

斐波那契搜索算法實現(xiàn)

斐波那契搜索算法如下: