数据结构学习之斐波那契查找-----------java实现

一、斐波那契数列介绍

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } ： 斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值0.618

二、斐波那契查找算法

2.1原理

同二分法差不多，只不过在mid的位置上作了处理。 在斐波那契查找算法中，mid的位置位于黄金分割点附近， 即 mid = low + F[ k - 1 ] - 1，其中F为斐波那契数列

关于F[ k - 1 ] - 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位置），都赋为原数组的high位置的值。 如： 原数组为{1,5,6,33,55,233,455}，长度n为7，若 F[ k ] - 1等于9，则应该将原数组扩容到9，多出的位置使用high位置的455填充，得到 ==> {1,5,6,33,55,233,455,455,455}

三、代码实现

3.1 定义斐波那契数列的生成方法

public static int maxSize = 20; public static int[] fib() { int[] f = new int[maxSize]; f[0] = 1; f[1] = 1; for (int i = 2; i < maxSize; i++) { f[i] = f[i - 1] + f[i - 2]; } return f; }

3.2 斐波那契查找(循环方式)

/** * 斐波那契查找(非递归方式) * @param arr 原数组 * @param key 目标值 * @return */ public static int fibSearch(int[] arr,int key){ int low=0; int high=arr.length-1; int k=0; //斐波那契分割数值的下标 int mid= 0; int f[]=fib();//获取斐波那契数列 //获取到斐波那契分割数组的下标 while (high > f[k] - 1){ k++; } //因为f[k]可能大于arr长度，因此需要构造一个新的数组，指向arr[] //不足的部分用0补充 int[] temp= Arrays.copyOf(arr,f[k]); //将用0填充的补充使用arr数组最后的数填充 for (int i=high+1;i<temp.length;i++){ temp[i]=arr[high]; } //循环查找 while (low < high){ mid = low +f[k-1] - 1; if (key<temp[mid]){ //向左查找 high = mid - 1; //f[k] = f[k-1] +f[k-2] //可以继续拆分成f[k-1]=f[k-2] +f[k-3],在f[k-1]左边继续查找 k--; }else if (key > temp[mid]){ //向右查找 low=mid+1; /* 说明： 1.f[k] = f[k-1] +f[k-2] 2.因为后面有f[k-2],所以可以继续拆分f[k-2]=f[k-3] +f[k-4] 3.即在f[k-2] 的前面进行查找，K-=2 4.即下载循环 mid=f[k-1-2] -1 */ k -=2; }else { //确定返回的是哪个小标 if (mid <= high){ return mid; }else { return high; } } } return -1; }

3.3测试

public static void main(String[] args) { int[] arr = {1, 8, 19, 89, 1000, 1234}; int i = fibSearch(arr, 1000);//返回目标位置下标 System.out.println(i); }

结果：4