一、斐波那契查找算法介绍
- 斐波那契数列（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;n<20;n++){ F[n]=F[n-1]+F[n-2]; } //输出结果 [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765] return F; } /**
* @Description: 使用非递归的方式编写斐波那契查找算法
* 利用公式 mid=low+F(k-1)-1
* @Param: arr 给定的原始数组
* findValue 需要查找的值
* @Author: xz
* @return:
* @Date: 2020/8/22 23:03
*/ public static int fibSearch(int[] arr,int findValue){ int low=0;//左边索引下标 int high=arr.length-1;//右边索引下标，输出 high:5 [1,8, 10, 89, 1000, 1234] int k=0;//斐波那契数列分割数值的下标 int midValue=0;//存放mid值 int[] F=fib();//获取到斐波那契数列 //获取到斐波那契分割数值的下标 while(high>F[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<temp.length;i++){ temp[i]=arr[high];//输出 temp: {1,8, 10, 89, 1000, 1234,1234,1234} } // 使用while来循环处理，找到我们的数 findValue while(low <= high){// 只要这个条件满足，就可以找 midValue=low+F[k-1]-1; if(findValue<temp[midValue]){//我们应该继续向数组的前面查找(左边) /**
* 说明为什么是 k--
* 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
*/ high=midValue-1; k--; }else if(findValue>temp[midValue]){// 我们应该继续向数组的后面查找(右边) /**
* 说明为什么是k -=2
* 1. 全部元素 = 前面的元素 + 后边元素
* 2. f[k] = f[k-1] + f[k-2]
* 3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
* 4. 即在f[k-2] 的前面进行查找 k -=2
* 5. 即下次循环 mid = f[k - 1 - 2] - 1
*/ low=midValue+1; k-=2; }else{ //找到 // 需要确定，返回的是哪个下标 if(midValue<=high){ return midValue; }else{ return high; } } } return -1; } }
2、运行main函数，结果如下
