詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)

發(fā)布時(shí)間：2020-10-19 07:50:12 來源：腳本之家閱讀：235 作者：失控的狗蛋~ 欄目：開發(fā)技術(shù)

一，斐波那契搜索算法簡述

斐波那契搜索(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ù)列來劃分范圍時(shí)，它會以與上述相同的比率進(jìn)行分割。

二，斐波那契搜索算法代碼實(shí)現(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時(shí)發(fā)生的。

接下來，我們比較數(shù)組的元素，并根據(jù)該比較，執(zhí)行以下操作之一：

將要搜索的元素與處的元素進(jìn)行比較fibonacciMinus2，如果值匹配，則返回索引。
如果elementToSearch比當(dāng)前元素時(shí)，我們移動在斐波納契數(shù)列上一步，而改變的值fibonacciNumber，fibonacciMinus1與fibonacciMinus2相應(yīng)。偏移量將重置為當(dāng)前索引。
如果elementToSearch比當(dāng)前元素小，我們繼續(xù)前進(jìn)后退兩步在斐波納契數(shù)列和改變的值fibonacciNumber，fibonacciMinus1與fibonacciMinus2相應(yīng)。

輸出結(jié)果：

詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)

時(shí)間復(fù)雜度

此搜索的最壞情況時(shí)間復(fù)雜度為O（log（N））。

空間復(fù)雜度

雖然我們需要將三個數(shù)字保存在斐波那契數(shù)列中并要搜索的元素，但我們需要四個額外的空間單位。

對空間的要求不會隨著輸入數(shù)組的大小而增加。因此，可以說斐波那契搜索的空間復(fù)雜度為O（1）。

當(dāng)除法運(yùn)算是CPU要執(zhí)行操作時(shí)，將使用此搜索。二進(jìn)制搜索之類的算法由于使用除法對數(shù)組進(jìn)行劃分，因此效果較差。

這種搜索的另一個好處是當(dāng)輸入數(shù)組的元素?zé)o法放入RAM中時(shí)。在這種情況下，此算法執(zhí)行的局部操作范圍可幫助其更快地運(yùn)行。

四，跳轉(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斐波那契搜索算法代碼實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java Fibonacci Search 內(nèi)容請搜索億速云以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持億速云！

向AI問一下細(xì)節(jié)

詳解Java Fibonacci Search斐波那契搜索算法代碼實(shí)現(xiàn)

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽