斐波那契(黄金分割法)查找算法(FibonacciSearch)

斐波那契(黄金分割法)查找算法(FibonacciSearch)

1.基本介绍

1)黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不大的效果。
2)斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例,无限接近 黄金分割值0.618
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UdI4iuY9-1593611639980)(en-resource://database/813:0)]

2.斐波那契(黄金分割法)原理

(1).斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列),如下图所示
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GghHDwbU-1593611639982)(en-resource://database/815:0)]
(2).对F(k-1)-1的理解:

  • 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质,可以得到 (F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 。该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1
  • 类似的,每一子段也可以用相同的方式分割
  • 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。
//获取到斐波那契分割数值的下标
        while (high > f[k] - 1){
            k++;
        }
import java.util.Arrays;

public class FibonacciSearch {

    public static int maxSize = 20;
    public static void main(String[] args) {
        int [] arr = {1,8, 10, 89, 1000, 1234};
        /*int f[] = fib();
        System.out.println(Arrays.toString(f));*/
        System.out.println("下标为:" + fibSearche(arr, 10));
    }

    //生成一个人fibonacci数列
    public static int[] fib(){
        int f[] = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 0; i < 20; i++) {
            if(i >= 2){
                f[i] = f[i-1] + f[i-2];
            }
        }
        return f;
    }

    //斐波那契查找算法
    public static int fibSearche(int a[], int key){
        int low = 0;
        int high = a.length - 1;
        int k = 0; //表示斐波那契分割数值的下标
        int mid = 0;
        int f[] = fib();

        //获取到斐波那契分割数值的下标
        while (high > f[k] - 1){
            k++;
        }

        //因为f[k] 可能大于a的长度,因此我们需要使用Arrays类,构造一个新的数组,并指向temp
        //不足的部分用0填充
        int temp[] = Arrays.copyOf(a, f[k]);
        //将填充的0 换位a
        for (int i  = a.length; i < f[k]; i++) {
            f[i] = a[high];
        }

        //循环找到key
        while (low <= high){ //当 low <= high 则一直循环
            mid = low +f[k-1] -1;

            if(key < temp[mid]){ //向左递归
                high -= 1;
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                //即 在 f[k-1] 的前面继续查找 k--
                //即下次循环 mid = f[k-1-1]-1
                k--;
            }else if(key > temp[mid]){ //向右递归
                low = mid + 1;
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-2] = f[k-3] + f[k-4]
                //4. 即在f[k-2] 的前面进行查找 k -=2
                //5. 即下次循环 mid = f[k - 1 - 2] - 1
                k -= 2;
            }else { //相等,找到了
                if(mid > high){
                    return a.length;
                }else {
                    return mid;
                }
            }
        }
        return -1;
    }
}
  • 结果
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qQmRfWUy-1593611639983)(en-resource://database/817:0)]

热门文章

暂无图片
编程学习 ·

lex yacc flex bison

简介 lex与yacc是两个在Unix下的分别作词法分析和语法分析的工具, Linux对应flex与bison。 Yacc 与 Lex 快速入门 flex 和bison的安装和使用 Windows下安装lex(flex)与yacc(bison)
暂无图片
编程学习 ·

Spring学习笔记(一):工厂模式

Spring学习笔记一:工厂模式1.简介2.工厂模式简单工厂设计通⽤⼯⼚的设计通用工厂的使用方式 1.简介 1.Spring是⼀个轻量级的 JavaEE 解决⽅案,整合众多优秀的设计模式。 2.EJB(Enterprise Java Bean):重量级框架,存在问题包括:运行环境苛刻,代码移植性差。 什么是轻量级?…
暂无图片
编程学习 ·

前端面试题及答案.全全全!!!---js

HTML——CSS——JS——es6——Vue——微信小程序-----------服务器----------nodeJS面试题1.基本数据类型有哪几种?undefined,null,boolean,string,number,Symbol(es6)2.引用数据类型有哪些?Object,Array3.JavaScript的typeof返回的数据类型?string number array object fun…
暂无图片
编程学习 ·

力扣-算法练习(Python)

9.回文数判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例3: 输入: 10 输出: fal…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

android热更新流程,kotlin高阶函数使用场景

工作2-5年的Android程序员该何去何从?方向:深入学习Android现在流行技术;浴火重生 Android,在占比80%市场为代表的智能手机的普及和发展,互联网行业如火如荼的进入了“移动”时代。但是近几年随着市场的逐渐成熟,整个移动互联网行业正处于增量下降丶存量厮杀的阶段。面对技…
暂无图片
郑州普通话 ·

Java Web 第八节 Javascript

这是阿锃总结黑马程序员的第八节的内容&#xff0c;主要是对于JavaScript的相关知识和操作&#xff0c;总结到这里&#xff0c;希望可以帮助到大家&#xff0c;若是大家也想要跟随黑马程序员学习JAVA WEB可以打开我的主页查找第一节的文章&#xff0c;里面有黑马程序员的视频链…
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…