【查找算法】斐波那契查找算法

文章目录

• 一：斐波那契推导公式
• • 1.1 斐波那契数列
  • 1.2 因此得出斐波那契数列的递推公式
  • 二：斐波那契(黄金分割法)查找算法
  • • 2.1 基本介绍
    • 2.2 原理
    • 2.3 对F(k-1)-1的理解
    • 三：代���实现

      一：斐波那契推导公式

      我们直接从现成的斐波那契数列入手，如下：

      1.1 斐波那契数列

      从上可知，从斐波那契数列第三项开始，每项的数值 = 前面两项数值之和，即 F(k) = F(k - 1) + F(k - 2)！

      1.2 因此得出斐波那契数列的递推公式

      二：斐波那契(黄金分割法)查找算法

      2.1 基本介绍

      1）黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。

      2）斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例，无限接近黄金分割值0.618

      2.2 原理

      斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列）

      2.3 对F(k-1)-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

      2）类似的，每一子段也可以用相同的方式分割

      3）但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

      三：代码实现

      package com.sysg.dataStructuresAndAlgorithms.find;import java.util.Arrays;/** * 斐波那契查找算法 */public class FibonacciSearch {    /**     * 斐波那契数列的长度     */    public static int MAX_SIZE = 20;    public static void main(String[] args) {        int[] array = {1, 8, 10, 89, 1000, 1234};        int index = fibonacciSearch(array, 1234);        System.out.println("index: " + index);    }    /**     * 使用非递归的方式编写斐波那契查找算法     *     * @param array     查找的数组     * @param findValue 需要查找的值     * @return 需要查找值的下标     */    public static int fibonacciSearch(int[] a, int findValue) {        int low = 0;        int high = a.length - 1;        //表示斐波那契数列的分割下标        int k = 0;        int mid = 0;        //获取斐波那契数列        int[] f = fib();        //获取到斐波那契分割数组的下标        while (high > f[k] - 1) {            k++;        }        //因为fib[k]的长度可能大于array的长度。构造一个数组来指向array        int[] temp = Arrays.copyOf(a, f[k]);        //使用array数组来填充我们的temp        // {1, 8, 10, 89, 1000, 1234 , 0 , 0 , 0} => {1, 8, 10, 89, 1000, 1234 , 1234 , 1234}        for (int i = high + 1; i