java数据结构和算法——斐波那契查找算法

一、斐波那契查找算法介绍

• 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

二、斐波那契查找算法定义

• 斐波那契数列指的是这样一个数列：
• 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597······
• 这个数列从第3项开始，每一项都等于前两项之和。

三、斐波那契(黄金分割法)原理

• 斐波那契查找原理与二分查找算法和插值查找算法类似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，公式 mid=low+F(k-1)-1,（F代表斐波那契数列,k代表斐波那契数列分割数值的下标）,如下图：

四、斐波那契算法应用案例需求

对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有返回-1。

五、斐波那契算法代码示例

1、代码

package com.rf.springboot01.dataStructure.search;

import java.util.Arrays;

/**
 * @description: 斐波那契查找算法示例
 * @author: xiaozhi
 * @create: 2020-08-22 22:47
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr={1,8, 10, 89, 1000, 1234};
        int index=fibSearch(arr,1);
        int index1=fibSearch(arr,1234);
        int index2=fibSearch(arr,108);
        System.out.println("1的数组下标=" +index);// 0
        System.out.println("1234的数组下标=" +index1);// 5
        System.out.println("108的数组下标=" +index2);// -1
    }
    /** 
    * @Description: 使用非递归方法得到一个长度为20的斐波那契数列
    *                利用公式 F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
    * @Param: [] 
    * @Author: xz  
    * @return: int[]
    * @Date: 2020/8/22 22:48  
    */ 
    public static int[] fib(){
        int[] F=new int[20];
        F[0]=1;
        F[1]=1;
        for(int n=2;nF[k]-1){ //输出  high:5 F:[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...]
            k++;
        }
        //因为F[k]值可能大于arr的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
        //不足的部分会使用0填充
        int[] temp =Arrays.copyOf(arr,F[k]); //输出 temp: {1,8, 10, 89, 1000, 1234,0,0}
        //实际上需求使用arr数组最后的数填充到temp数组中
        for(int i=high+1;i