首页 数据结构和算法

斐波那契查找数列是一串按照F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)这一条件递增的一串数字:

1、1、2、3、5、8、13、21 ... ...

我们在学习递归时候已经对此进行了了解,我们发现,两个相邻项的比值会逐渐逼近0.618 —— 黄金分割比值。将这个思路运用到查找算法上,就实现了斐波那契查找算法。

斐波那契数列最重要的一个性质是每个数都等于前两个数之和(从第三个数字开始)

也就是一个长度为f(n)的数组,它能被分成f(n-1)和f(n-2)这两半,而f(n-1)又能被分为f(n-2)和f(n-3)这两半,直到分到1和1为止(f(1)和f(2))。

斐波那契查找算法

这里我们发现,二分查找,插值查找和斐波那契查找的基础其实都是:对数组进行分割, 只是各自分割的标准不同: 二分是从数组的一半分, 插值是按预测的位置分, 而斐波那契是按它数列的数值分。

三个数组以及它们之间的关系

了解斐波那契查找的算法实现, 最重要的是理解“三个数组”之间的关系,它们分别是:

  • 待查找数组 (a)
  • 斐波那契数组(fiboArray)
  • 填充后数组(filledArray)

斐波那契数组

要按斐波那契数分割, 我们当然要创建一个容纳有斐波那契数的数组,那么,怎么确定这个数组的呢?

其实,数组大小只要刚好能满足我们的需要就可以了,斐波那契数组的长度,取的是包含有大于等于待查找数组长度数值的最小长度。原数组长4则取5,长6则取8,长13取13,以此类推。

其次我们要考虑的是: 我们的数组长度不可能总是满足斐波那契儿波那契数的, 例如5、8、13、21等是斐波那契数, 但我们的数组长度可能是6,7,10这些非斐波那契数, 那这时候怎么办呢? 总不能对长度为10的待查找数组按照8和13进行第一次分割吧?此时,我们就需要用到填充数组。

填充数组

我们按照上面选定的斐波那契数组的最大值, 创建一个等于该长度的填充数组, 将待查找数组的元素依次拷贝到填充数组中, 剩下的部分用原待查找数组的最大值填满。这就是填充数组。

我们进行查找操作的并不是原待排序数组, 而是对应的填充数组。

斐波那契查找算法

总结查找过程

  • 根据待查找数组长度确定斐波那契数组的长度(或最大元素值)
  • 根据待查找数组长度创建该长度的斐波那契数组,再通过F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)生成斐波那契数列为数组赋值
  • 以斐波那契数组的最大值为长度创建填充数组,将原待排序数组元素拷贝到填充数组中来, 如果有剩余的未赋值元素, 用原待排序数组的最后一个元素值填充(保持顺序)
  • 针对填充数组进行关键字查找, 如果进行填充操作则需要在查找成功后判断该元素是否来源于后来填充的那部分元素

代码实现

import java.util.Arrays;

public class FibonacciSearch {

    public static int maxSize = 20;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = new int[] { 1, 8, 10, 89, 1000, 1234};
        int n = fibSearch(arr, 1234);
        System.out.println(n);
    }

    // 因为mid = low + F(k-1)-1,需要使用斐波那契数列
    // 因此我们需要获取到一个斐波那契数列

    // 此处使用非递归方式构造一个斐波那契数列
    public static int[] getFib() {
        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;
        int k = 0; // 表示斐波那契分割数值的下标
        int mid = 0; // 存放中值
        int f[] = getFib(); // 获取到斐波那契数列
        // 获取斐波那契分割数值的下标
        while (high >= f[k] - 1) {
            k++;
        }
        // 因为f[k]可能大于数组的长度,因此需要用Arrays类,构造一个新的数组
        // 并指向a[],不足的部分会使用0填充
        int[] tmp = Arrays.copyOf(a, f[k]);
        // 对填充为0部分重置为原数组末尾的数值
        for (int i = high + 1; i < tmp.length; i++) {
            tmp[i] = a[high];
        }

        // 使用while来循环处理,找到key
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if(key < tmp[mid]) { //我们应该继续向左查找
                high = mid -1;
                //说明:
                //1.全部元素 = 前面的元素 + 后面元素
                //2.f[k]= f[k-1] + f[k-2]
                //因为前面有f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                //即在f[k-1]的前面继续查找 k--; f(k-1)是左半边的长度
                //即下次循环 mid = f[k-1-1]-1
                k--; //k=k-1
            }else if(key > tmp[mid]) { //我们应该往右边查找
                low = mid + 1;
                //说明:
                //1.全部元素 = 前面的元素 + 后面的元素
                //2.f[k]= f[k-1] + f[k-2]
                //3.因为后面有f[k-2],所以可以继续拆分f[k-2] = f[k-3] + f[k-4]
                
                k-=2; //k=k-2 f(k-2)是右半边的长度
            }else { //找到了
                //需要确定返回的是哪个下标
                if(mid <= high) {  //说明取到了填充部分
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;  //未查到
    }
}

文章来源于:https://zhuanlan.zhihu.com/p/31895830
参考:https://www.cxyxiaowu.com/9561.html




文章评论