栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

斐波那契查找的思路与代码实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

斐波那契查找的思路与代码实现

思路

斐波那契数列片段:

有序数组:

数组长度11,斐波那契数列大于11的最小值是13,将数组扩容到长度为13,增加的两个位置存储的值为数组值的最大值99:

此时k=7,f(k)=13,f(k-1)=8,f(k-2)=5,将数组分成两个部分,左边长度是f(k-1),右边长度是f(k-2),我们要查找的位置下标是f(k-1)-1:

代码示例和单元测试
public class FibonacciSearch {

    public static int search(int[] arr, int key) {
        if (arr == null || arr.length == 0)
            return -1;
        // pos是我们要查找的位置,类似折半查找的mid,k是斐波那契数列的位置下标
        int low = 0, high = arr.length - 1, pos, k = 0, len = arr.length;
        if (key < arr[low] || key > arr[high])
            return -1;
        if (len == 1)
            return arr[0] == key ? 0 : -1;
        // 数组长度对应的斐波那契数列的下标
        while (len > f(k))
            k++;
        int[] arr1;
        int len1 = f(k);
        if (len < len1) { // 需要将数组扩容至长度为f(k)
            arr1 = new int[len1];
            System.arraycopy(arr, low, arr1, low, len);
            for (int i = len; i < len1 - 1; i++)
                arr1[i] = arr1[high];
        } else {
            arr1 = arr;
        }
        while (low <= high) {
            if (k < 2) { // 斐波那契数列下标小于2时需要特殊处理
                pos = low + f(k) - 1;
            } else {
                pos = low + f(k - 1) - 1;
            }
            if (key < arr1[pos]) {
                high = pos - 1;
                k -= 1;
            } else if (key > arr1[pos]) {
                low = pos + 1;
                k -= 2;
            } else {
                // 如果数组进行了扩容,可能出现pos > len - 1的情况
                return Math.min(pos, len - 1);
            }
        }
        return -1;
    }

    public static int f(int i) {
        if (i < 0) {
            throw new IllegalArgumentException();
        }
        if (i < 2) {
            return i;
        }
        return f(i - 2) + f(i - 1);
    }

    public static void main(String[] args) {
        testCase5();
    }

    public static void testCase() {
        int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
        int key = 101;
        System.out.println(search(arr, key));
    }

    public static void testCase1() {
        int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
        int key = -1;
        System.out.println(search(arr, key));
    }

    public static void testCase2() {
        int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
        int key = 36;
        System.out.println(search(arr, key));
    }

    public static void testCase3() {
        int[] arr = {1};
        int key = 1;
        System.out.println(search(arr, key));
    }

    public static void testCase4() {
        int[] arr = {1, 2};
        int key = 2;
        System.out.println(search(arr, key));
    }

    public static void testCase5() {
        int[] arr = {0, 1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(search(arr, arr[i]));
        }
    }
}

斐波那契查找除了数组自身的查找开销,还有斐波那契数列的构建开销和数组扩容的开销。个人感觉不是太实用。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950608.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号