四、斐波那契（黄金分割法）查找算法

参考下面两份资料

https://www.cnblogs.com/sha-Pao-Zi/p/16315064.htmlhttps://www.cnblogs.com/sha-Pao-Zi/p/16315064.html

36-查询算法-斐波那契查找3-分解1数组准备_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1ga411b7qF?p=37&spm_id_from=pageDriver&vd_source=c01240addcba226237f3c4781490fbae

      黄金分割点是指把一条线段分割成两部分，使其中一部分与全长之比等于另一部分与这一部分之比。取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽，因此称为黄金分割，也称中外比。

     斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618，即将mid值设置成神器的黄金分割点(0.618)的位置

    这个数列的后一个数是前两个数之和，如8=5+3

4.1 原理

      与二分查找法、插值查找法相似，仅仅改变了中间节点(mid)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近

       即mid=low+F(k-1)-1,其中F代表斐波那契数列，low是数组最左侧元素的索引，k代表斐波那契数列的第几个元素

对F(k-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位置），都赋为n位置的值即可。

while(n>fib(k)-1)k++;

注意, 此时斐波那契数列是存放在数组中的, 所以会用F[]表示, 一定要注意跟F()的不同, 比如: F[6] =13 = F(7), F[0] = 1 = F(1)

4.2  难点解析图

其实对于(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 及 mid=low+f(k-1)-1  还有另外一种理解方式，我不知道对不对，但是我感觉很有道理

    最开始的 数组的长度是f(k) = f(k-1)+f(k-2),此时代表的是长度，一定要注意

   但是当我们获取下数组的时候就需要长度-1，数组的原因 变成了  (F[k]-1)

   然后我们把数组分成了三部分，左侧的部分的数组下标到f[k-1]-1,右侧到f[k-2]-1，但是此时我们中间还有一个mid，所示再+1（占一个下标的位子），故(F[k-1]-1)+(F[k-2]-1)+1

  我觉得还是用上面的图理解更为合适，上面的图是从很多地方整理结合出来的，下面的文字是我自己想的有点不太对

4.3 代码

public class FibSearch {private static int maxSize = 20;public static void main(String[] args) {int[] arr = {1,8,10,89,1000,1234};System.out.println(fibSearch(arr,1234));}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;}/*** @param a   数组* @param key 我们需要查找的关键码值* @return 返回对应的下标，如果没有-1*/public static int fibSearch(int[] a, int key) {int low = 0;int high = a.length - 1;  //high下标对应的数据就是数组中最大的数int k = 0;  //表示斐波那契分割数值的下标int mid = 0;  //存放mid值int f[] = fib(); //获取斐波那契数列//       获取到斐波那契分割数值的下标
//       为什么不写a.length()>f[k]? 而是两边同时-1成为high >f[k]-1 ？
//           应该也是可以的  这个的目的就是找出一个f[k]>=a.length的while (high > f[k] - 1) {
//           进入循环相当于没找到k++;
//            退出的条件  a.length()<=f[k]}//      f[k]的值可能大于数组a的长度，因此我们需要使用Arrays类构造一个新的数组（临时数组）并指向a[]
//        if (f[k] > a.length) {  } 此时这里不用if语句判断f[k] > a.length，因为因为上面while的缘故f[k]>=a.length是一定的
//      将a数组拷贝到temp数组，并且temp数组的长度是f[k]的值，int[] temp = Arrays.copyOf(a, f[k]);
//       新扩充的地方用0补齐，但是我们需要用a数组的最后一位补齐，我们还得改一下temp数组for (int i = a.length; i < temp.length; i++) {temp[i] = a[a.length - 1];}while (low <= high) {
//           只要这个条件满足就一直找mid = low + f[k - 1] - 1;  //黄金分割点if (key < temp[mid]) {
//              向左找high = mid - 1;
//              为什么是k--？
//                  全部元素=f[k-1]+f[k-2]
//                  f[k] = f[k-1] + f[k-2]
//                  因为前面有f[k-1]个元素，这个f[k-1]依然可以再拆分
//                  带入公式变为f[k-1]=f[k-1-1]+f[k-1-2] 在前面的一部分找一个黄金分割点 高一知识k--;} else if (key > temp[mid]) {
//               向右low = mid + 1;
//              为什么是k=k-2?
//                全部元素=f[k-1]+f[k-2]
//                我们后面有k-2个元素，再对k-2进行拆分，把k-2个元素的部分想象成整个部分来看
//                f[k-2]=f[k-2-1]+f[k-2-2]  在后一部分找一个黄金分割点、满足斐波那契查找
//                最终就是下面的公式k = k - 2;} else {
//              找到了，但是需要判断返回的下标if (mid <= a.length-1) {
//                表示这个就是在原始的数组内找到的，并不是在扩容之后的内容return mid;}else {
//                在扩容的内容里找到的return a.length-1;}}}
//      整个while都没有返回表示没有找到对应的内容，则返回-1return -1;}}