詳解Java Fibonacci Search斐波那契搜索算法代碼實現(xiàn)
一， 斐波那契搜索算法簡述
斐波那契搜索(Fibonacci search) ，又稱斐波那契查找，是區(qū)間中單峰函數(shù)的搜索技術(shù)。
斐波那契搜索采用分而治之的方法，其中我們按照斐波那契數(shù)列對元素進(jìn)行不均等分割。此搜索需要對數(shù)組進(jìn)行排序。
與二進(jìn)制搜索不同，在二進(jìn)制搜索中，我們將元素分成相等的兩半以減小數(shù)組范圍-在斐波那契搜索中，我們嘗試使用加法或減法來獲得較小的范圍。
斐波那契數(shù)列的公式是：
Fibo(N)=Fibo(N-1)+Fibo(N-2)
此系列的前兩個數(shù)字是Fibo(0) = 0和Fibo(1) = 1。因此，根據(jù)此公式，該級數(shù)看起來像是0、1、1、2、3、5、8、13、21。。。這里要注意的有趣觀察是：
Fibo(N-2)大約是1/3的Fibo(N)Fibo(N-1)大約是2/3的Fibo(N)
因此，當(dāng)我們使用斐波那契數(shù)列來劃分范圍時，它會以與上述相同的比率進(jìn)行分割。
二，斐波那契搜索算法代碼實現(xià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;
}
三，斐波那契搜索算法總結(jié)
首先從找到斐波那契數(shù)列中最接近但大于數(shù)組長度的數(shù)字開始。這fibonacciNumber是在13剛好大于數(shù)組長度10時發(fā)生的。
接下來，我們比較數(shù)組的元素，并根據(jù)該比較，執(zhí)行以下操作之一：
- 將要搜索的元素與處的元素進(jìn)行比較fibonacciMinus2，如果值匹配，則返回索引。
- 如果elementToSearch比當(dāng)前元素時，我們移動在斐波納契數(shù)列上一步，而改變的值fibonacciNumber，fibonacciMinus1與fibonacciMinus2相應(yīng)。偏移量將重置為當(dāng)前索引。
- 如果elementToSearch比當(dāng)前元素小，我們繼續(xù)前進(jìn)后退兩步在斐波納契數(shù)列和改變的值fibonacciNumber，fibonacciMinus1與fibonacciMinus2相應(yīng)。
輸出結(jié)果：
時間復(fù)雜度
此搜索的最壞情況時間復(fù)雜度為O（log（N））。
空間復(fù)雜度
雖然我們需要將三個數(shù)字保存在斐波那契數(shù)列中并要搜索的元素，但我們需要四個額外的空間單位。
對空間的要求不會隨著輸入數(shù)組的大小而增加。因此，可以說斐波那契搜索的空間復(fù)雜度為O（1）。
當(dāng)除法運算是CPU要執(zhí)行操作時，將使用此搜索。二進(jìn)制搜索之類的算法由于使用除法對數(shù)組進(jìn)行劃分，因此效果較差。
這種搜索的另一個好處是當(dāng)輸入數(shù)組的元素?zé)o法放入RAM中時。在這種情況下，此算法執(zhí)行的局部操作范圍可幫助其更快地運行。
四，跳轉(zhuǎn)搜索算法完整代碼
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);
}
}
到此這篇關(guān)于詳解Java Fibonacci Search斐波那契搜索算法代碼實現(xiàn)的文章就介紹到這了,更多相關(guān)Java Fibonacci Search 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
java使用RSA加密方式實現(xiàn)數(shù)據(jù)加密解密的代碼
這篇文章給大家分享java使用RSA加密方式實現(xiàn)數(shù)據(jù)加密解密，通過實例代碼文字相結(jié)合給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值，需要的朋友參考下2019-11-11
Spring Boot console log 格式自定義方式
這篇文章主要介紹了Spring Boot console log 格式自定義方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
使用任何已有的工具,都沒有直接使用 get set 方式進(jìn)行,對象轉(zhuǎn)換的速度快,雖然get set 方式代碼對一些比較麻煩,但是效率要高一些的,推薦使用 MapStruct 方式.,需要的朋友可以參考下2021-05-05
這篇文章主要介紹了@Autowierd(自動裝配)的使用說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要介紹了Java Iterator（迭代器）的相關(guān)資料，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
淺談SpringCache與redis集成實現(xiàn)緩存解決方案
本篇文章主要介紹了淺談SpringCache與redis集成實現(xiàn)緩存解決方案，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
淺談Java中Collection和Collections的區(qū)別
下面小編就為大家?guī)硪黄獪\談Java中Collection和Collections的區(qū)別。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-08-08
在使用學(xué)習(xí)使用 Spring過程中，當(dāng)我們要實現(xiàn)一個功能的時候，先應(yīng)該考慮的是有沒有相應(yīng)的注解是實現(xiàn)對應(yīng)功能的，Spring 中很多功能的配置都是可以依靠注解實現(xiàn)的，而本篇中介紹的是使用注解來存儲 Bean 對象2023-07-07
拼圖游戲是一種智力類游戲,玩家需要將零散的拼圖塊按照一定的規(guī)律組合起來,最終拼成完整的圖案,這篇文章主要給大家介紹了關(guān)于用Java編寫一個簡單的拼圖游戲,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-06-06
這篇文章主要介紹了教你如何寫springboot接口,Spring?Boot是由Pivotal團隊提供的全新框架，其設(shè)計目的是用來簡化新Spring應(yīng)用的初始搭建以及開發(fā)過程。該框架使用了特定的方式來進(jìn)行配置，從而使開發(fā)人員不再需要定義樣板化的配置,需要的朋友可以參考y一下2022-01-01