查找算法之斐波那契查找_斐波那契查找树

作者：正经夜光杯 | 2024-07-19 16:37:54

踩

斐波那契查找树

前言

查找算法是一种用于在数据集合中查找特定元素的算法。在计算机科学中，查找算法通常被用于在数组、链表、树等数据结构中查找目标元素的位置或者判断目标元素是否存在。
查找算法的目标是在尽可能短的时间内找到目标元素，以提高程序的效率和性能。常见的查找算法包括但不限于二分查找、哈希表查找、线性查找、二叉查找树等。

一、查找算法预备知识

查找算法分类

1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
无序查找：被查找数列有序无序均可；
有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）
需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。
对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。

Pi：查找表中第i个数据元素的概率。
Ci：找到第i个数据元素时已经比较过的次数。

二、斐波那契查找

斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、・・・・，在数学上，斐波那契被递归方法如下定义：F (1)=1，F (2)=1，F (n)=f (n-1)+F (n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数 F [n]，将原查找表扩展为长度为 F[n](如果要补充元素，则补充重复最后一个元素，直到满足 F[n] 个元素)，完成后进行斐波那契分割，即 F [n] 个元素分割为前半部分 F [n-1] 个元素，后半部分 F [n-2] 个元素，找出要查找的元素在那一部分并递归，直到找到。
通过利用黄金分割原理来确定查找的位置。与二分查找类似，但是斐波那契查找对比较次数的期望值略低于二分查找。

算法步骤：

构建斐波那契数列，直到数列中的最大值大于等于要查找的数组长度。
找到最接近且不超过数组长度的斐波那契数值，记为F(k)。
根据F(k)将原数组扩展为长度为F(k)的新数组，将多出的元素用原数组中最后一个元素填充。
初始化两个指针low和high，分别指向数组的起始和结束位置。
计算中间位置的索引mid，根据目标值与arr[mid]的大小关系，更新low和high指针的位置。
重复以上步骤，直到找到目标元素或者low > high为止。

  public static int[] fibonacci(){
        int[] f = new int[20];
        int i =0;
        f[0] = 1;
        f[1] = 1;
        for(i=2;i<MAXSIZE;i++){
            f[i] = f[i-1]+f[i-2];
        }
        System.out.println(Arrays.toString(f));
        return f;
    }
    
    public static int fibonacciSearch(int[] data,int key){
        int low = 0;
        int high = data.length-1;
        int mid = 0;

        //斐波那契分割数值下标
        int k = 0;

        //序列元素个数
        int i=0;

        // 获取斐波那契数列
        int[] f = fibonacci();

        //获取斐波那契分割数值下标
        while(data.length>f[k]-1){
            k++;
        }
        //创建临时数组
        int[] temp = new int[f[k]-1];
        for(int j=0;j<data.length;j++){
            temp[j] = data[j];
        }

        //序列补充至f[k]个元素
        //补充的元素值为最后一个元素的值
        for(i=data.length;i<f[k]-1;i++){
            temp[i]=temp[high];
        }

        for(int j:temp){
            System.out.print(j+" ");
        }
        System.out.println();

        while( low <= high )
        {
            // low：起始位置
            // 前半部分有f[k-1]个元素，由于下标从0开始
            // 则-1 获取 黄金分割位置元素的下标
            mid = low + f[k-1] - 1;
              if( temp[mid] > key )
            {
                // 查找前半部分，高位指针移动
                high = mid - 1;
                //将 k 减去 1，表示我们要查找前半部分。
                // 因为前半部分有 f[k-1] 个元素，所以我们更新 k = k - 1;。
                k = k - 1;
            }else if( temp[mid] < key )
            {
                // 查找后半部分，低位指针移动
                low = mid + 1;
                //将 k 减去 2，表示我们要查找后半部分。
                // 因为后半部分有 f[k-2] 个元素，所以我们更新 k = k - 2;。
                k = k - 2;
            }else{
                //如果为真则找到相应的位置
                if( mid <= high )
                {
                    return mid;
                }else{
                    //出现这种情况是查找到补充的元素
                    //而补充的元素与high位置的元素一样
                    return high;
                }
            }
        }
        return -1;
    }


    public static void test4() {
        int[] arr = {12, 11, 15, 50, 7, 65, 3, 99,100,101};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        int result = fibonacciSearch(arr, 101);
        if (result != -1) {
            System.out.println("目标元素 " + 101 + " 在数组中的索引位置为: " + result);
        } else {
            System.out.println("目标元素 " + 101 + " 未找到");
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94