查找算法——斐波那契（黄金分割法） Java实现-蒲公英云

查找算法——斐波那契（黄金分割法） Java实现

水深无声 2023-03-13 13:02 17阅读 0赞

黄金分割点：取前三位 0.618
菲波那契数列 {1,1,2,3,5,8,13}，我们会发现俩个相邻数的比值无限接近于0.618
斐波那契查找原理与前两种（二分、插值）相似，仅改变了中间结点(mid) 的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即middle = left + F(k-1)-1 (F代表斐波那契数列)。

由斐波那契数列 F (k) =F(x-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 的两段，从而中间位置为 middle = left + 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++;
```
}

代码实现：
首先使用一个方法用于计算菲波那契数列：

public static int maxsize = 20;
    //创建斐波那契数列
    public static int[] fibarr() { 
        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;
    }

随后定义一个查找算法：

// 传入数组，待查数据，返回下标索引值
    public static int fib(int[] arr, int value) { 
        int left = 0;
        int right = arr.length - 1;
        int k = 0; // 菲波那切数列分割数值的下标
        int middle = 0;
        int f[] = fibarr();
        // 获取k值
        while (right > f[k] - 1) { 
            k++;
        }
        // f[k]可能会大于arr的长度，使用一个新的数组，指向arr
        // 不足的地方使用0填充，实际上需要使用arr最后一个数进行填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        for (int i = right + 1; i < temp.length; i++) { 
            temp[i] = arr[right];
        }
        // 循环查找到这个value值
        while (left <= right) { 
            middle = f[k - 1] - 1;// 拿到下标进行比较
            if (value < temp[middle]) { 
                // 向左查找
                right = middle - 1;
                k--;
            } else if (value > temp[middle]) { 
                // 向右查找
                left = middle + 1;
                k -= 2;
            } else { 
                // 需要确定返回的是哪个下标 middle or right
                if (middle <= right) { 
                    return middle;
                } else { 
                    return right;
                }
            }
        }
        return -1;
    }