一， 斐波那契搜索算法簡述
斐波那契搜索(Fibonacci search) ，又稱斐波那契查找，是區間中單峰函數的搜索技術。
斐波那契搜索采用分而治之的方法，其中我們按照斐波那契數列對元素進行不均等分割。此搜索需要對數組進行排序。
與二進制搜索不同，在二進制搜索中，我們將元素分成相等的兩半以減小數組范圍-在斐波那契搜索中，我們嘗試使用加法或減法來獲得較小的范圍。
斐波那契數列的公式是：
Fibo(N)=Fibo(N-1)+Fibo(N-2)
此系列的前兩個數字是Fibo(0) = 0和Fibo(1) = 1。因此，根據此公式，該級數看起來像是0、1、1、2、3、5、8、13、21。。。這里要注意的有趣觀察是：
Fibo(N-2) 大約是1/3的 Fibo(N)Fibo(N-1) 大約是2/3的 Fibo(N)因此，當我們使用斐波那契數列來劃分范圍時，它會以與上述相同的比率進行分割。
二，斐波那契搜索算法代碼實現
/**
*
* @param integers
* @param elementToSearch
* @return
*/
public static int fibonacciSearch(int[] integers, int elementToSearch) {
int fibonacciMinus2 = 0;
int fibonacciMinus1 = 1;
int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
int arrayLength = integers.length;
while (fibonacciNumber < arrayLength) {
fibonacciMinus2 = fibonacciMinus1;
fibonacciMinus1 = fibonacciNumber;
fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
}
int offset = -1;
while (fibonacciNumber > 1) {
int i = Math.min(offset+fibonacciMinus2, arrayLength-1);
if (integers[i] < elementToSearch) {
fibonacciNumber = fibonacciMinus1;
fibonacciMinus1 = fibonacciMinus2;
fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
offset = i;
}
else if (integers[i] > elementToSearch) {
fibonacciNumber = fibonacciMinus2;
fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2;
fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
}
else return i;
}
if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch)
return offset+1;
return -1;
}
三，斐波那契搜索算法總結
首先從找到斐波那契數列中最接近但大于數組長度的數字開始。這fibonacciNumber是在13剛好大于數組長度10時發生的。
接下來，我們比較數組的元素，并根據該比較，執行以下操作之一：
輸出結果：
時間復雜度
此搜索的最壞情況時間復雜度為O（log（N））。
空間復雜度
雖然我們需要將三個數字保存在斐波那契數列中并要搜索的元素，但我們需要四個額外的空間單位。
對空間的要求不會隨著輸入數組的大小而增加。因此，可以說斐波那契搜索的空間復雜度為O（1）。
當除法運算是CPU要執行操作時，將使用此搜索。二進制搜索之類的算法由于使用除法對數組進行劃分，因此效果較差。
這種搜索的另一個好處是當輸入數組的元素無法放入RAM中時。在這種情況下，此算法執行的局部操作范圍可幫助其更快地運行。
四，跳轉搜索算法完整代碼
If you are interested, try it.
public class SearchAlgorithms {
/**
*
* @param integers
* @param elementToSearch
* @return
*/
public static int fibonacciSearch(int[] integers, int elementToSearch) {
int fibonacciMinus2 = 0;
int fibonacciMinus1 = 1;
int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
int arrayLength = integers.length;
while (fibonacciNumber < arrayLength) {
fibonacciMinus2 = fibonacciMinus1;
fibonacciMinus1 = fibonacciNumber;
fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
}
int offset = -1;
while (fibonacciNumber > 1) {
int i = Math.min(offset+fibonacciMinus2, arrayLength-1);
if (integers[i] < elementToSearch) {
fibonacciNumber = fibonacciMinus1;
fibonacciMinus1 = fibonacciMinus2;
fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
offset = i;
}
else if (integers[i] > elementToSearch) {
fibonacciNumber = fibonacciMinus2;
fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2;
fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
}
else return i;
}
if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch)
return offset+1;
return -1;
}
/**
* 打印方法
* @param elementToSearch
* @param index
*/
public static void print(int elementToSearch, int index) {
if (index == -1){
System.out.println(elementToSearch + " 未找到");
}
else {
System.out.println(elementToSearch + " 在索引處找到: " + index);
}
}
//測試一下
public static void main(String[] args) {
int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);
}
}
到此這篇關于詳解Java Fibonacci Search斐波那契搜索算法代碼實現的文章就介紹到這了,更多相關Java Fibonacci Search 內容請搜索億速云以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
