斐波那契查找

介绍

斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。斐波那契查找的时间复杂度还是O(log 2 n )，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定

实现

迭代版

:::details 点击查看代码

/**
 * @description: 
 * 一、创建斐波那契数列
      - 公式: F(n) = F(n-1) + F(n-2) 

   二、在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n]
      (如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素)

        a. 获取有序表元素个数在斐波那契数列中最接近的最大数列值  k ,初始值为 0

            - 条件为 : end < f[k] - 1
            
        b. f[k] 可能大于 array 的长度，因此需要补充数组

            - 条件为 ：[array.length-1+1,f[k]-1] 补充 array 中的最后一个元素


    三、完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元
       素，找出要查找的元素在那一部分并递归，直到找到

       a. 定义 start、end 用来表示 array 数组中每段的 [start,end]

       b. 定义黄金分割点：middle = start + F(k-1) - 1

       c. 开始循环查找

            - 如果 value < array[middle] 向左开始寻找

                - end = middle - 1
                - key = key - 1

            - 如果 value > array[middle] 向右开始寻找

                - start = middle + 1
                - key = key - 2
            - 如果 value = array[middle] 

                return middle
      
 */
function Fibonacci() {
    const maxSize = 40;
    const fib = [];
    fib[0] = 1;
    fib[1] = 1;
    for (let i = 2; i < maxSize; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib;
}
function FibonacciSearch(array, value) {
    let start = 0;
    let end = array.length - 1;
    let middle = 0;
    let k = 0;
    let fib = Fibonacci();
    while (end > fib[k] - 1) {
        k++;
    }
    for (let i = end + 1; i < fib[k] - 1; i++) {
        array[i] = array[end];
    }
    while (start <= end) {
        middle = start + fib[k - 1] - 1;
        if (value < array[middle]) {
        end = middle - 1;
        k--;
        } else if (value > array[middle]) {
        start = middle + 1;
        k = k - 2;
        } else {
        return middle;
        }
    }
    return -1;
}

const array = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(FibonacciSearch(array, 10));
console.log(array[FibonacciSearch(array, 10)]);

:::

介绍​

实现​

迭代版​

介绍

实现

迭代版