3

数据结构与算法__02--斐波那契查找，数组中元素个数的说明为F[k]-1

 1 year ago
source link: https://blog.51cto.com/husheng/5914924
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

1 斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

2 斐波那契查找

2.1 定义

斐波那契搜索(Fibonacci search) ，又称斐波那契查找，是区间中单峰函数的搜索技术。斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。

2.2 常规基本步骤

  1. 构建斐波那契数列，对查找表填充，以查找表最后一个元素填充至最接近的斐波那契数列中的元素 F(k)-1
  2. 确定查找点 mid = low+F(k-1)-1；
  3. 判断中间值 temp[mid] 和目标值的关系，确定下一步策略：
    • 如果目标值小于中间值，说明目标值在左区间。由于左区间长度为 F(k-1)，因此 k 应该更新为k-1，然后再次执行 2、3 两步；
    • 如果目标值大于中间值，说明目标值在右区间。由于右区间长度为 F(k-2)，因此 k 应该更新为 k-2，然后再次执行 2、3 两步；
    • 如果目标值等于中间值，说明找到了目标值。但此时还需判别该目标值是原查找表中的元素还是填充元素：
  4. 判断填充值位置
    • 如果是原查找表中的元素，直接返回索引；
    • 如果是填充元素，则返回原查找表的最后一个元素的索引，即 temp.length-1。（因为扩展数组是以原查找表最后一个元素来填充，如果目标值是填充元素，则说明原查找表最后一个元素值就是目标值）

3 问题解决

韩顺平老师代码中数组中元素个数的说明为F[k]，经过分析我们可以发现实际使用的只有F[k]-1，所以temp数组中元素个数为F[k]-1更为合理。查找过程如下图所示：

数据结构与算法__02--斐波那契查找，数组中元素个数的说明为F[k]-1_ci
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;
}
public static int fibSearch(int[] a, int key) {
    ......
    //创建新数组的部分代码
    int[] temp = Arrays.copyOf(arr, f[k]-1);
    for(int i = high + 1; i < temp.length; i++) {
        temp[i] = a[high];
    } 
    ......
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK