详解Java Fibonacci Search斐波那契搜索算法代码实现

一, 斐波那契搜索算法简述

斐波那契搜索(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时发生的。

接下来,我们比较数组的元素,并根据该比较,执行以下操作之一:

  • 将要搜索的元素与处的元素进行比较fibonacciMinus2,如果值匹配,则返回索引。
  • 如果elementToSearch比当前元素时,我们移动在斐波纳契数列上一步,而改变的值fibonacciNumber,fibonacciMinus1与fibonacciMinus2相应。偏移量将重置为当前索引。
  • 如果elementToSearch比当前元素小,我们继续前进后退两步在斐波纳契数列和改变的值fibonacciNumber,fibonacciMinus1与fibonacciMinus2相应。

输出结果:

时间复杂度

此搜索的最坏情况时间复杂度为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 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2020-10-12

Java打印斐波那契前N项的实现示例

题外 由于idea原因 用注解test无法在控制台上输入所以写死到程序里了,版本都30.9102了为什么还是这样啊,intelJ你们该反思了!!! 用intelJ IDEA的小伙伴有遇到这种测试情况吗,如果项目上有测试用例需要自己单元测试,怎么解决控制台输入问题(@test情况下),直接改main方法的那个就算了.~~ 斐波那契的认识 斐波那契数列前2项为1,从第3项开始为该项的前2项和. eg:1,1,2,3,5,8- f(n)=f(n-1)+f(n-2) 代码参考 import org.ju

递归之斐波那契数列java的3种方法

本文实例为大家分享了java递归之斐波那契数列的具体代码,供大家参考,具体内容如下 第一种.普通写法 public class Demo { public static void main(String[] args) { int num1 = 1; int num2 = 1; int num3 = 0; System.out.println(num1); System.out.println(num2); for (int i = 1; i < 10; i++) { num3 = num1 +

java实现斐波那契数列的3种方法

先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案.去面试的时候,由于面试前天晚上11点钟才到阿里巴巴指定面试城市,找到旅馆住下基本都1点多,加上晚上完全没有睡好,直接导致第二天面试效果很不好(对于那些正在找工作的大虾们不要向小虾一下悲剧,提前做好准备还是很重要滴),面试大概进行了一个多小时(面试结束回去的时候基本走路都快睡着了,悲催!!),面试快结束的时候面试官问的我问题就是关于费波那西数列,当时头脑完全浆糊,只知道要设置三个变量或者用List先初始化,当写到for循环的

Java实现Fibonacci(斐波那契)取余的示例代码

Description Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1. 当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少. Input 多组测试数据 输入包含一个整数n.1 <= n <= 1,000,000. Output 每组输出一行,包含一个整数,表示Fn除以10007的余数. Sample Input 10 22 Sample Output 55 7704 利用余数三大定理: 1.余数的加法定理 a与b的和除以c的余数,等于

java数学归纳法非递归求斐波那契数列的方法

本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege

java编程经典案例之基于斐波那契数列解决兔子问题实例

本文实例讲述了java基于斐波那契数列解决兔子问题.分享给大家供大家参考,具体如下: 题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? package com.java.recursion; /** * @描述 三种方法实现斐波那契数列 * @项目名称 Java_DataStruct * @包名 com.java.recursion * @类名 Fibonacci * @author chenli

java实现fibonacci数列学习示例分享(斐波那契数列)

输出:1  1  2  3  5 复制代码 代码如下: public class FibonaciTest { public static void main(String[] args) {  Fibonaci(5); } public static void Fibonaci (int count) { int[] num = new int[count];  num[0] = num[1] = 1; for (int i = 2; i < count; i++) {   num[i] =

JAVA递归与非递归实现斐波那契数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列.因数学家列昂纳多·斐波那契(Leonardoda Fibonacci[1] )以兔子繁殖为例子而引入,故又称为"兔子数列",指的是这样一个数列:0.1.1.2.3.5.8.13.21.34.--在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)在现代物理.准晶体结构.化学等领域,斐波纳契数列都有直接的应用,为此,美国数学会从1963起

三种java编程方法实现斐波那契数列

题目要求:编写程序在控制台输出斐波那契数列前20项,每输出5个数换行 //java编程:三种方法实现斐波那契数列 //其一方法: public class Demo2 { // 定义三个变量方法 public static void main(String[] args) { int a = 1, b = 1, c = 0; System.out.println("斐波那契数列前20项为:"); System.out.print(a + "\t" + b + &qu

python实现斐波那契数列的方法示例

介绍 斐波那契数列,又称黄金分割数列,指的是这样一个数列:0.1.1.2.3.5.8.13.21.--在数学上,斐波纳契数列以如下递归的方法定义: F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*) . 1. 元组实现 fibs = [0, 1] for i in range(8): fibs.append(fibs[-2] + fibs[-1]) 这能得到一个在指定范围内的斐波那契数列的列表. 2. 迭代器实现 class Fibs: def __init__

php实现斐波那契数列代码分享

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........ 这个数列从第3项开始,每一项都等于前两项之和. F0=0,F1=1,Fn=F(n-1)+F(n-2) 递归版和非递归版. <?php function fib($n){ $array = array(); $array[0] = 1; $arra

C语言求Fibonacci斐波那契数列通项问题的解法总结

一:递归实现   使用公式f[n]=f[n-1]+f[n-2],依次递归计算,递归结束条件是f[1]=1,f[2]=1. 二:数组实现   空间复杂度和时间复杂度都是0(n),效率一般,比递归来得快. 三:vector<int>实现   时间复杂度是0(n),时间复杂度是0(1),就是不知道vector的效率高不高,当然vector有自己的属性会占用资源. 四:queue<int>实现   当然队列比数组更适合实现斐波那契数列,时间复杂度和空间复杂度和vector<int&g

Java递归实现斐波那契数列

程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合.一般来说,递归需要有边界条件.递归前进段和递归返回段.当边界条件不满足时,递归前进:当边界条件满足时,递归返回.--这是百度百