介绍
斐波那契查找（Fibonacci Search）又叫黄金分割查找，斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。
不同之处还是mid的计算方法，mid不再是中间或者插值得到，而是位于黄金分割点的附近：mid = left + f(k-1) - 1。要使用斐波那契查找，就要先构建一个斐波那契数列，斐波那契数列的长度就和原始数组保持一致即可，主要是用来获取中间索引mid。
left表示原始数组左边索引，初始的时候就是0，构建好斐波那契数组，我们要让f(k-1) - 1指向数组的最后一个索引，然后从斐波那契数组中根据mid = left + f(k-1) - 1来获取中间索引。
创建一个新数组，长度为f(k)，因为长度为f(k)的数组才满足f(k) = f(k-1) + f(k-2)，才能使用斐波那契数列去获取mid索引。将原始数组的所有数据拷贝过去，如果f(k)的值大于原始数组的长度，那就将超出长度的部分用原始数组的最后一个数填充。根据mid索引去上面创建的新数组中获取元素进行比较。
如果这个数比要查找的数更小，那说明在原始数组的mid的左边，那就让right = mid - 1，同时k要减1，因为刚才我们是在斐波那契数列f(k)的位置获取的索引，在f(k)的前面，有f(k-1)个元素，将这个f(k-1)个元素继续拆分，就可以拆成f(k-1) = f(k-2) + f(k-3)，再根据mid = left + f(k-1-1) - 1重新获取mid。
如果这个数比要查找的数更大，就让left = mid + 1，同时k要减2，因为上面说了，斐波那契数列满足f(k) = f(k-1) + f(k-2)，在f(k)的左边，有f(k-1)个元素，右边有f(k-2)个元素，继续拆分就变成了f(k-2) = f(k-3) + f(k-4)，所以是k-2，再根据mid = left + f(k-1-2) - 1重新获取mid。
如果mid对应是数刚好等于被查找数，那说明找到了，mid索引就是就被查找元素的位置，但是不能直接返回mid，因为上面说了，f(k)可能比原始数组长度更长，超出部分用原始数组最后一个元素填充，如果直接返回mid，此时mid可能指向的是超出部分的元素，用这个mid去原始数组中找，就越界了，所以应该返回mid和right中较小的那个。
//获取斐波那契数列 public static int[] fib(int length) { int[] fibArr = new int[length]; fibArr[0] = 1; fibArr[1] = 1; for (int i = 2; i < length; i++) { fibArr[i] = fibArr[i - 1] + fibArr[i - 2]; } return fibArr; } //斐波那契查找算法 public static int fibonacciSearch(int[] arr, int num) { int[] f = fib(arr.length); //获取斐波那契的数组 int left = 0; //原始数组左边的下标 int right = arr.length - 1; //原始数组右边的下标 int k = 0; //斐波那契数组的下标 while (f[k] - 1 < right) { //指向数组的最后索引 k++; } //由于f(k)不是步长为1的递增数列，所以可能出现f(k) - 1的值大于原始数组最后一个索引的情况 //比如原始数组最大索引为4，那么此时f(k)就等于5，所以要构造一个新数组，不够的部分会用0填充 //如果多余部分用0填充可能会造成查找失败，因此，需要将0的部分填充为原来数组中的最后一个元素 int[] temp = Arrays.copyOf(arr, f[k]); for (int i = right + 1; i < temp.length; i++) { temp[i] = arr[right]; } while (left <= right) { //循环查找 int mid = left + f[k - 1] - 1; //获取mid if (num < temp[mid]) { //往左查找 right = mid - 1; k -= 1; } else if (num > temp[mid]) { //往右查找 left = mid + 1; k -= 2; } else { return mid <= right ? mid : right; //返回下标 } } return -1; }
