侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

使用斐波那契查找算法在有序序列(数组)中查找元素的位置

孔子说JAVA
2022-07-24 / 0 评论 / 0 点赞 / 46 阅读 / 3,795 字 / 正在检测是否收录...

和插值查找法一样,斐波那契查找(Fibonacci Search)算法也是有序表的一种查找方式,同样属于二分查找的一个优化,它是利用了黄金分割原理(斐波那契数列)来实现的。一般情况下斐波那契查找算法的速度比二分法要快的多,能有效减少查找循环的次数。改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。

00959aed744a1bb7275f6898ca22ef0a

1、斐波那契查找(Fibonacci Search)算法介绍

用途:能在大量的数据中找到自己想找的元素,减少查找的循环的次数。

条件:斐波那契查找(Fibonacci Search)算法类似于二分查找法和插值查找,必须是有序列表。对于非有序序列,可以先进行排序后再使用插值查找算法查找。

原理

  • 对一个有序数列进行查找的时候,二分法(即折半查找)是利用中间值middle来一步步缩小搜索的范围,直至找到最终结果。时间复杂度:O(log(n))。
  • 插值查找算法同二分法类似,唯独中间值middle的计算方式不一样,该middle值会尽可能的接近我们要查找的值,减少查找的次数,时间复杂度一样为 O(log(n))。
  • 斐波那契查找(Fibonacci Search)算法和二分法及插值算法一样,不同的是middle值不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表斐波那契数列)。

斐波那契数列

斐波那契数列:即1,1,2,3,5,8,13…,从第三个数开始,后面的数都等于前两个数之和,而斐波那契查找就是利用的斐波那契数列来实现查找的。初始化的斐波那契数列最后一位要大于等于数组元素的size-1。

查找步骤

假设表中有 n 个元素,查找过程为获取区间的下标 mid=low + fibonacci[k - 1] - 1 ,对 mid 的关键字与给定值的关键字比较:

  1. 如果与给定关键字相同,则查找成功,返回mid和high的最小值;
  2. 如果给定关键字大,向右查找并减小2个斐波那契区间;
  3. 如果给定关键字小,向左查找并减小1个斐波那契区间;
  4. 重复过程,直到找到关键字(成功)或区间为空集(失败)。

2、实现方式

2.1 实例1

import org.junit.Test;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 */
public class FibonacciSearch {
    /**
     * 有序的数组
     */
    public int[] elements = new int[]{1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
    /**
     * 对应的斐波拉契数组,数组的最大值>=elements.length-1
     * 本例中elements.length-1==9,所以对应的fibonacci数组的最大值>=9, 取值为13
     */
    public int[] fibonacci = new int[]{1, 1, 2, 3, 5, 8, 13};

    @Test
    public void test() {
        System.out.println(fibonacciSearch(88));
    }

    /**
     * 斐波那契查找的实现
     *
     * @param key 要查找的数据
     * @return 查找到的索引, 或者-1 表示查找到
     */
    public int fibonacciSearch(int key) {
        //最小索引
        int low = 0;
        //最大索引
        int high = elements.length - 1;
        //不在范围内,直接返回-1
        if (elements[low] > key || elements[high] < key) {
            return -1;
        }

        int k = 0, i, mid;
        /*计算high位于斐波那契数列的位置 */
        //这里high为9,fibonacci[5]<9<fibonacci[6] ,取大的,即k=6
        while (high > fibonacci[k]) {
            k++;
        }

        /*扩展数组*/
        //扩展原数组,长度扩展为fibonacci[k]=13,即多加了三个位置elements[10],elements[11],elements[12]
        elements = Arrays.copyOf(elements, fibonacci[k]);
        //为了保证数组的顺序,把扩展的值都设置为原始数组的最大值
        for (i = high + 1; i < elements.length; i++) {
            elements[i] = elements[high];
        }
        /*开始斐波那契查找*/
        while (low <= high) {
            System.out.println("------");
            /* 计算当前分隔的下标索引,取的是黄金分割点 7-4-2-1-0  7-10*/
            mid = low + fibonacci[k - 1] - 1;
            /* 若查找记录小于当前分隔记录 */
            if (key < elements[mid]) {
                /* 最高下标调整到分隔下标mid-1处 */
                high = mid - 1;
                /* 斐波那契数列下标减一位 */
                k = k - 1;
            }
            /* 若查找记录大于当前分隔记录 */
            else if (key > elements[mid]) {
                /* 最低下标调整到分隔下标mid+1处 */
                low = mid + 1;
                /* 斐波那契数列下标减两位 */
                k = k - 2;
            } else {
                /* 若mid <= high则说明mid即为查找到的位置,返回mid */
                /* 若mid>high说明是补全数值,返回high */
                return Math.min(mid, high);
            }
        }
        return -1;
    }
}

2.2 实例2

import java.util.Arrays;

/**
 * 斐波那契查找算法
 */
public class FibonacciSearch {
    public static int Maxsize = 20;

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 12, 15};
        int val = findVal(arr, 12);
        System.out.println(val);

    }

    //用函数定义一个斐波那契数列
    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 findVal(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        int f[] = fib();// 调用的斐波那契数列
        int k = 0;//斐波那契数列所以
        int mid = 0;
        while (high > f[k]) {
            k++;
        }
        // 因为斐波那契数组的f[k]值可能大于arr数组的长度,
        // 因此我们要使用Arrays类,构造一个新的数组,并指向arr[], 不足的部分会使用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 实际上需求用arr最后的值来进行补充
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = arr[high];
        }
        // 使用while循环,找到数key, 只要这个条件满足,就可以找
        while (low <= high) {
            System.out.println("---");
            //中间下标
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {
                // 要找的数小于中间值,说明在数组的左边 fibIndex--;
                high = mid - 1;
                k--;
            } else if (key > temp[mid]) {
                // 要找的值大于中间值说明在数组的右边
                // fibonacci[fibIndex]=fibonacci[fibIndex-1]+fibonacci[fibIndex-2];
                // fibonacci[fibIndex-1] 为数组左边的值 fibonacci[fibIndex-2]为数组右边的值
                low = mid + 1;
                k -= 2;
            } else {
                // 注意:这里要进行判断返回时是哪个下标
                // 如果mid<=high,返回mid; 如果mid>high,返回high;
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }
        }
        return -1;
    }
}

3、总结

2022119144513847-1658592758419

如上图,斐波那契查找的特点就是左侧半区范围大于右侧半区范围。如果要查找的记录在mid右侧,则左侧的数据都不用再判断了,不断反复进行下去,对处于右侧当中的大部分数据,其工作效率要高一些。 所以尽管斐波那契查找的时间复杂也为O(logn),但就平均性能来说,斐波那契查找要优于二分查找。可惜如果是最坏情况,比如这里key=1,那么始终都处于左侧长半区在查找,则查找效率要低于二分查找。

还有比较关键的一点,二分查找是进行加法与除法运算(mid=(low+high)/2),插值查找进行复杂的四则运算(mid=low+(highlow) * (key-a[low])/(a[high]-a[low])),而斐波那契查找只是最简单加减法运算(mid=low+F[k-1]-1),在海量数据的查找过程中,这种细微的差别可能会影响最终的查找效率,但是斐波那契额查找同样需要额外的空间。

0

评论区