斐波那契查找算法的实现（又称黄金分割查找法；【java语言实现】）

核心思想

由斐波那契数列 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
将mid作为顺序表的分割点
由于mid的确认过程不涉及除法，仅仅需要进行加或者减；理论上比二分查找法消耗要小，速度快

实现代码

package com.zhaojinlei.test;import java.util.Arrays;/** * className:FibonacciSearch * * @author:ZHAOJINLEI * @version:0.1 * @date:2020/9/517:17 * @since:jdk1.8 */public class FibonacciSearch {    public static void main(String[] args) { //测试1 int[] ser = {0,3,5,9,12,13,26,66,99}; int index = search(ser, 26); System.out.println("{0,3,5,9,12,13,26,66,99}中查找26："); System.out.println("index:"+index +"  value:"+ser[index]); System.out.println(); //测试2 int[] ser1 = {0,3,5,9,12,13,26,66,99,109,110,112,116,225,336,995,1000,1001,1002,1030}; int index1 = search(ser1, 995); System.out.println("{0,3,5,9,12,13,26,66,99,109,110,112,116,225,336,995,1000,1001,1002,1030}中查找995："); System.out.println("index:"+index1 +"  value:"+ser1[index1]);    }    //创建一个含n个数的斐波那契数列    public static int[] createFibonacci(int n) { int[] ints = new int[n]; ints[0] = 1; ints[1] = 1; for (int i = 2; i < ints.length; i++) {     ints[i] = ints[i - 1] + ints[i - 2]; } return ints;    }    public static int search(int ser[], int elem) { int n = 10;  //初始斐波那契数列长度10 int[] fibs = createFibonacci(n); while (fibs[fibs.length - 1] < ser.length) {//斐波那契数列长度不够，进行扩容（每次扩2倍）     n *= 2;     fibs = createFibonacci(n); } int low = 0; int high = ser.length; int k = fibs.length - 1; int mid; while (fibs[k] - 1 > ser.length) {//找到符合要求的k的最小值     k--; } k++; int[] ints = Arrays.copyOf(ser,fibs[k]-1);//复制原数组 for (int i = ser.length; i < ints.length; i++) {//超出原数组的最大索引的位置填充原数组最大值     ints[i] = ser[ser.length - 1]; } while (low < high) {     //检查两端     if(ints[low] == elem)  return low;     if(ints[high] == elem)  return high;     //黄金分割点     mid = low + fibs[k - 1];     if (ints[mid] == elem){  if(mid<ser.length-1){      return ser.length-1;  }else {      return mid;  }     }     //低区查找     if(ints[mid]>elem){  high = mid-1;  k--;     }     //高区查找     if(ints[mid]<elem){  low = mid+1;  k-=2;     } } return -1;    }}

测试结果