1、斐波那契查找：斐波那契搜索也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。 同样地，斐波那契查找也属于一种有序查找算法，必须在有序的结构中才能进行查找。 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。
2、斐波那契查找的时间复杂度：斐波那契查找的时间复杂度为O( logn )。
3、斐波那契查找的实现：
//查找算法 斐波那契查找 该查找方法的效率要低于插入查找的效率但是高于二分查找的效率//查找效率：插入查找 > 斐波那契查找 > 二分查找 > 顺序查找public class FeibonacciSearch {public static void main(String[] args) {int[] arr = {1, 5, 7, 10, 40, 50, 56, 67, 79, 80, 99};int key = 50;int index = feibonacciSearch(arr, key);System.out.println("index:" + index);}//斐波那契查找private static int feibonacciSearch(int[] arr, int key) {int low = 0; int high = arr.length - 1;int mid = 0; //是arr数组或者temp数组的索引int[] f = getFeiArr(); //获取斐波那契数列int k = 0; //表示斐波那契数列的索引while(arr.length > f[k]) {k++;//要求斐波那契数列中k位置的值是斐波那契数列中最小的大于high的值//最后斐波那契数列中k位置的值 就是我们要创建的新数组的长度}//重新创建一个数组 将arr数组复制进新数组 新数组长度为斐波那契数列k位置的值//要保证该值是能将arr数组包含进去且最小的值int[] temp = Arrays.copyOf(arr, f[k]);//将新数组多余出来的位置的值 全部填成原数组high位置的值for(int i = high + 1; i < temp.length; i++) {temp[i] = high;}while(low <= high) { //当low大于high 则说明没有找到指定元素mid = low + f[k - 1] - 1; //为mid赋值，mid的值为：low加上斐波那契数列k-1位置的值减1//如果要查找的值大于新数组mid位置的值 low指针就等于mid+1 //使k指向斐波那契数列中构成现temp数组的长度的值的小的那一部分的位置if(key > temp[mid]) { low = mid + 1;k -= 2;//如果要查找的值小于新数组mid位置的值 high指针就等于mid-1 //使k指向斐波那契数列中构成现temp数组的长度的值的大的那一部分的位置}else if(key < temp[mid]) {high = mid - 1;k -= 1;//如果以上条件不满足 mid位置的值就是要寻找的值 但是还有做一个判断}else {//如果mid小于等于high 则说明mid就是要找的值的索引if(mid <= high) {return mid;//如果mid大于等于high 则说明high才是要找的值在原数组的索引}else {return high;}}}//如果没有找到 就返回-1return -1;}//获取斐波那契数列private static int[] getFeiArr() {int[] f = new int[20];f[1] = 1;f[2] = 1;for(int i = 2; i < f.length; i++) {f[i] = f[i - 1] + f[i - 2];}return f;}}
4、运行结果：