详解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 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

  • 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数学归纳法非递归求斐波那契数列的方法

    本文实例讲述了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实现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实现斐波那契数列的3种方法

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

  • 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 Search斐波那契搜索算法代码实现

    一, 斐波那契搜索算法简述 斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术. 斐波那契搜索采用分而治之的方法,其中我们按照斐波那契数列对元素进行不均等分割.此搜索需要对数组进行排序. 与二进制搜索不同,在二进制搜索中,我们将元素分成相等的两半以减小数组范围-在斐波那契搜索中,我们尝试使用加法或减法来获得较小的范围. 斐波那契数列的公式是: Fibo(N)=Fibo(N-1)+Fibo(N-2) 此系列的前两个数字是Fibo(0) = 0和Fibo

  • 详解Java实现的k-means聚类算法

    需求 对MySQL数据库中某个表的某个字段执行k-means算法,将处理后的数据写入新表中. 源码及驱动 kmeans_jb51.rar 源码 import java.sql.*; import java.util.*; /** * @author tianshl * @version 2018/1/13 上午11:13 */ public class Kmeans { // 源数据 private List<Integer> origins = new ArrayList<>()

  • 详解JAVA调用WCF服务的示例代码

    这一篇将要解决java中调用WCF的问题,使用的依旧是上一篇中托管在IIS中的WCF服务,本来我是打算用axis来写这篇文章的,可就在我开始之前,无意中发现了在java包中自带的wsimport工具,用起来是极为爽快,而且也节省了配置axis的时间.所以,就它吧 其实在有了wsimport,在java调用wcf的时候是极为简单的,当然这是建立在使用不太复杂的服务的情况下,如果还要考虑安全验证.发布订阅等问题,还是相对复杂的,但是这三篇文章没准备写那么多,只是想能把跨平台这三个字真的应用在实践中

  • Java版超大整数阶乘算法代码详解-10,0000级

    当计算超过20以上的阶乘时,阶乘的结果值往往会很大.一个很小的数字的阶乘结果就可能超过目前个人计算机的整数范围.如果需求很大的阶乘,比如1000以上完全无法用简单的递归方式去解决.在网上我看到很多用C.C++和C#写的一些关于大整数阶乘的算法,其中不乏经典但也有很多粗糙的文章.数组越界,一眼就可以看出程序本身无法运行.转载他人文章的时候,代码倒是仔细看看啊.唉,粗糙.过年了,在家闲来蛋疼,仔细分析分析,用Java实现了一个程序计算超大整数阶乘.思想取自网上,由我个人优化和改进. 这个方法采用"数

  • 详解Java实现分治算法

    目录 一.前言 二.分治算法介绍 三.分治算法经典问题 3.1.二分搜索 3.2.快速排序 3.3.归并排序(逆序数) 3.4.最大子序列和 3.5.最近点对 四.结语 一.前言 在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱.但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了 当然如果你觉得各个部分

  • 详解Java分布式系统中一致性哈希算法

    业务场景 近年来B2C.O2O等商业概念的提出和移动端的发展,使得分布式系统流行了起来.分布式系统相对于单系统,解决了流量大.系统高可用和高容错等问题.功能强大也意味着实现起来需要更多技术的支持.例如系统访问层的负载均衡,缓存层的多实例主从复制备份,数据层的分库分表等. 我们以负载均衡为例,常见的负载均衡方法有很多,但是它们的优缺点也都很明显: 随机访问策略.系统随机访问,缺点:可能造成服务器负载压力不均衡,俗话讲就是撑的撑死,饿的饿死. 轮询策略.请求均匀分配,如果服务器有性能差异,则无法实现

  • 详解Java实现拓扑排序算法

    目录 一.介绍 二.拓扑排序算法分析 三.拓扑排序代码实现 一.介绍 百科上这么定义的: 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前.通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列.简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序. 为什么会有拓扑排序?拓

  • 详解Java双轴快速排序算法

    目录 一.前言 二.回顾单轴快排 三.双轴快排分析 3.1.总体情况分析 3.2.k交换过程 3.3.收尾工作 四.双轴快排代码 一.前言 首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用.所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行. 二.回顾单轴快排 单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn). 而快排的具体思路也很

  • 详解Java如何实现FP-Growth算法

    FP-Growth算法的Java实现 这篇文章重点讲一下实现.需要两次扫描来构建FP树 第一次扫描 第一次扫描,过滤掉所有不满足最小支持度的项:对于满足最小支持度的项,按照全局支持度降序排序. 按照这个需求,可能的难点为如何按照全局支持度对每个事务中的item排序. 我的实现思路 扫描原数据集将其保存在二维列表sourceData中 维护一个Table,使其保存每个item的全局支持度TotalSup 在Table中过滤掉低于阈值minSup的项 将Table转换为List,并使其按照Total

  • 详解Java如何实现数值校验的算法

    给定一个字符串如何判断它是否为数值类型?例如:字符串+100.5e2.-123.3.1416以及-1E-16都表示数值,为数值类型,但12e.1a3.14.1.2.3.+-5以及12e+5.4都不是. 本文将带着大家实现这个判断算法,欢迎各位感兴趣的开发者阅读本文. 实现思路 我们先来看一下数值的定义规则:表示数值的字符串遵循模式A[.[B]][e|EC]或者.B[e|EC],其中: A为数值的整数部分 B紧跟着小数点为数值的小数部分 C紧跟着e或者E为数值的指数部分 在小数里可能没有数值的整数

随机推荐