斐波那契（黃金分割法）查找算法

（一）算法簡介

（1）斐波那契數列

在講算法之前，我們先介紹一下斐波那契數列，該數列公式為F(K) = F(k-1) + F(k-2)，即 1、1、2、3、5、8、13、21……。我們還知道，F(k-1)/f(K)隨著K的遞增，該數越來越接近黃金分割比例，所以該方法也叫黃金分割法。

（2）查找算法

對于一個數組來說，如果數組長度為斐波那契數列中的某一個數字，那么我們就可以用黃金分割比例來分割該數組。當然，如果數組長度沒有達到要求，那么我們可以嘗試它擴大來滿足要求，所以這就是算法的要求。

其實，該算法的本質也還是二分法，只不過跟插入排序法一樣，也是將目標的mid值改變成其它的，以至于分割的結果不一樣，查找的效果也不一樣。

那么具體是怎樣分割的呢？

這里用圖片直觀理解一下：

也就是說，真正需要我們做的是找到這個mid，這里給出公式：mid = F(k-1)-1，你也可以從圖片中看出來，數組下表是從：0~F[k]-1，將原來的分成兩半，再比較來查找。

（二）代碼解釋

（1）main 主方法，不多解釋

public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 99, 100 };System.out.println("index = " + FibSearch(arr, 99)); }

（2）獲取一個斐波那契數組，簡單不多解釋

public static int maxSize = 20;public static int[] getFibonacci() {int[] fib = new int[maxSize];fib[0] = 1;fib[1] = 1;for (int i = 2; i < maxSize; ++i) {fib[i] = fib[i - 1] + fib[i - 2];}return fib; }

(3)斐波那契查找算法

public static int FibSearch(int[] arr, int value) {int low = 0;int high = arr.length - 1;int mid = 0;int[] fib = getFibonacci();int k = 0;while (high >= fib[k] - 1) {k++;}int[] tmp = Arrays.copyOf(arr, fib[k]);for (int i = arr.length; i < fib[k]; ++i) {tmp[i] = arr[high];}while (low <= high) {mid = low + fib[k - 1] - 1;if (value < tmp[mid]) {high = mid - 1;k--;} else if (value > tmp[mid]) {low = mid + 1;k -= 2;} else {if (mid <= high) {return mid;} else {return high;}}}return -1; }

• 在15行之前都是對數組的一個拷貝、擴容處理，以到達黃金分割的目的
• 后面mid = low + fib[k - 1] - 1就可以成功定位mid的位置，最后比較，查找
• 注意一點：最后如果找到還要判斷一下，如果返回的是在原數組之內的下標，可以直接返回，如果返回的是數組之外的下標，得返回原數組最后那個，即 high

位置，最后比較，查找

• 注意一點：最后如果找到還要判斷一下，如果返回的是在原數組之內的下標，可以直接返回，如果返回的是數組之外的下標，得返回原數組最后那個，即 high

總結

以上是生活随笔為你收集整理的查找算法之斐波那契查找算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。