精华内容
下载资源
问答
  • 斐波那契查找

    2021-03-15 23:47:02
    斐波那契查找(Fibonacci Search)又叫黄金分割查找,斐波那契查找和二分查找、插值查找也类似,数组也要是有序的。 不同之处还是mid的计算方法,mid不再是中间或者插值得到,而是位于黄金分割点的附近:mid = left...

    介绍

    斐波那契查找(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;
    }
    

     

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,107
精华内容 842
关键字:

斐波那契查找