精华内容
下载资源
问答
  • 斐波那契查找算法——深入理解,详细推导
    千次阅读
    2020-06-18 13:47:33

    斐波那契查找算法又称黄金分割查找算法。黄金分割点是把一条线段分成两个部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。

    了解斐波那契查找算法就必须了解斐波那契数列,例如这样一组数列{1,1,2,3,5,8,13,21,34,55}。其中每项的值等于前两项之和,两个相邻数字的比列无线接近与0.618。

    关于斐波那契算法,(以下截图来自韩顺平老师数据结构与算法的教学视频)链接
    在这里插入图片描述
    补充:理解mid = low + F(k - 1) - 1对于后面写程序至关重要,其中式子F[K] - 1 = (F[k - 1] - 1) + (F[k - 2] - 1) + 1;这里面‘1‘就代表mid。

    (这段是重点:)
    可以看到,斐波那契查找算法的思路就是把一个斐波那契数列映射到原需要查询的数列。通过将斐波那契数列中的每一项的值看成是一个数列中元素的个数,其中,斐波那契数列中的每一项减去1就代表原数列中的下标,因为原数列起始下标是从0开始的。关键是要理解斐波那契是如何对原数列进行划分的。它的划分规则就是借助于一个斐波那契数列。例如有一斐波那契数列{1,1,2,3,5,8,13},假设长度13是我们需要查询的原数列。根据斐波那契的规则:每项等于前两项之和,比如这里的13 = 8 + 5。然后根据这个规则映射到对原数组划分,则长度13的原数组划分为长度8,和5两个部分。所以对应的下标就是一部分{0到7}(这部分就是F[k - 1],其中的k表示斐波那契数列的下标),另一部分{8到12}(这一部分就是F[k - 2],k同前)。所以根据公式mid = low + F(k - 1) - 1,算出mid = 0 + 8 - 1 等于7,所以原查询数列下标为7是中间值,这也验证了上述的划分结果没有错误,接下来如果没有找到就需要在第一轮划分上接着划分,过程是一样的,都需要借助斐波那契数列。到此,相信读者已经明白了整个过程。(笔者自认为这一段讲述是非常清晰、成功的哈哈哈)。

    还有一点需要注意:由于斐波那契数列中的每一项我们看成是一个数列的元素个数,而斐波那契数列中的每一项的值是固定了的,但它却不包含所有的值。所以我们需要将原需要查询的数列扩容到大小离斐波那契数列中最接近的那一个数。例如斐波那契数列中有13这么一个项,而我此时的数列长度只有12,所以需要将原数列扩容到13。至于扩容的过程,在代码中体会吧。到此为止,是不是特别清晰明了了?

    最后给出完整的代码,细节就在代码中慢慢体会吧:

    /**
         * 斐波那契查找算法非递归实现
         *
         * @param arr   待查询的数组
         * @param value 查询的值
         * @return 位置结果(下标)
         */
    
        public static int fibonacciSearch(int[] arr, int value) {
            int low = 0;//起始下标
            int height = arr.length - 1;//最末尾的下标
            int mid = 0;//初始化中间值
            int[] f = fib();//获取斐波那契数列
            int k = 0;//斐波那契数组下标
            //这个循环的作用就是找到待查询数组大小在斐波那契数列中最接近的值
            while (height > f[k] - 1) {
                k++;
            }
            //数组扩容
            int[] temp = Arrays.copyOf(arr, f[k]);
            //默认扩容的后面结果都是0,这个循环的作用就是将扩容出来的地方都存储原数列最后一个数据
            //例如:{1,3,4,35,66,0,0,0} ===》{1,3,4,35,66,66,66,66}
            for (int i = height + 1; i < temp.length; i++) {
                temp[i] = arr[height];
            }
            //开始循环查找,直到找到查找值的下标
            while (low <= height) {
                mid = low + f[k - 1] - 1;//mid求算算法
                if (value < temp[mid]) {
                    height = mid - 1;
                    //说明:为什么k - 1
                    //当value < temp[mid]所以向左查找,而f[k - 1]代表左部分
                    k -= 1;
                } else if (value > temp[mid]) {
                    low = mid + 1;
                    //说明:为什么k - 2
                    //当value > temp[mid]所以向右查找,而f[k - 2]代表右部分
                    //为什么又要k - 1呢?
                    // 这里经过测试这样才能防止数组下标越界。如果待查数列个数是奇数,如果一直 - 2,到最后k就为等于0
                    //再执行上面的f[k - 1]就会越界,由于斐波那契数列的第一项和第二项都是1所以当k = 2时直接- 1就好了
                    //这样也避免了下标越界
                    if (k == 2) {
                        k -= 1;
                    } else {
                        k -= 2;
                    }
                } else {
                    //这里的if分支语句判断的是查找的元素是不是扩充部分,由于扩充部分的值就是原数列最后一位的值,
                    //而且扩充部分在原数列中是不存在的,所以直接用原数列最后一位的位置代替
                    if (mid <= height) {
                        return mid;
                    } else {
                        return height;
                    }
                }
            }
            //没有找到
            return -1;
        }
    

    小小总结一下吧:不管是斐波那契查找算法还是之前谈到的插值查询算法,思想都是跟二分查找思想类似,只是查询mid的算法不同,而斐波那契查找算法是需要通过斐波那契数列间接求算的。

    以上代码过程,注释给的非常详细了。慢慢分析,相信读者一定会有所收获。

    更多相关内容
  • 对比分析折半查找与Fibonacci查找算法。 ①二分查找算法 算法思想: 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较 如果两者相等,则查找成功; 否则利用中间位置记录将表分成前、后...

    对比分析折半查找与Fibonacci查找算法

    ①二分查找算法

    算法思想:

    首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较

    如果两者相等,则查找成功;

    否则利用中间位置记录将表分成前、后两个子表,

    如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,

    否则进一步查找后一子表。

    重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    例:假设已知有序数组为{1,2,4,5,7,8,11,12,15,19,21},查找元素为11,则查找过程如下。

    在这里插入图片描述
    算法时间复杂度:O(log n)

    代码实现:

    int search(int guan[], int imp, int n)
    {
    	int mid;
    	int low = 1, high = n;
    	while (low <= high)
    	{
    		mid = (low + high) / 2;
    		if (imp == guan[mid])
    			return mid;
    		else if (imp < guan[mid])
    			high = mid - 1;
    		else if (imp > guan[mid])
    			low = mid + 1;
    	}
    	return 0;
    }
    

    ②Fibonacci查找算法

    斐波那契查找也要求数据是有序的。斐波那契查找采用和二分查找相似的区间分割策略,都是通过不断的分割区间缩小搜索的范围。不过它的分割方法不是二分查找中原有的中值 mid 的求解方式,其 mid 不再代表中值,而是代表了黄金分割点,要搞清楚这一点,我们先要介绍Fibonacci数列;

    Fibonacci数列:

    又名黄金分割数列(因为它的前一项与后一项的比值随着数字数量的增多逐渐逼近黄金分割比值0.618)

    斐波那契数列以如下递推的方法定义:
    F ( 0 ) = 0 , F ( 1 ) = 1 , F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n ≥ 2 , n ∈ N ∗ ) F(0)=0, F(1)=1, F(n)=F(n−1)+F(n−2)(n≥2,n∈N∗) F(0)=0,F(1)=1F(n)=F(n1)+F(n2)(n2,nN)
    斐波那契数列从第三项开始,每一项都等于前两项之和

    例如: F = { 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , . . . }

    Fibonacci查找算法的思想

    根据斐波那契数列的特点,而我们可以利用它来做区间分割:可以将一个长度为 F(n) 的数组看作左右两数组,左边数组长度是 F(n-1),右边数组长度是 F(n-2)。
    在这里插入图片描述

    那如何找到这个中间值mid呢?

    不难看出,它就等于最左边的位置+F(n-1)

    但是数组元素下标从0开始,所以要**-1**

    故斐波那契查找算法的查找点的计算公式如下:

    m i d = l e f t + F ( n − 1 ) − 1 m i d = l e f t + F ( n − 1 ) − 1 mid=left+F(n1)1

    所以,对于每一个数组,我们首先需要确认它的长度是不是Fibonacci数列中的一个数F(n),如果是,我们计算它的mid位置,就可以把它分成F(n-1)和F(n-2)

    那如果不是怎么办呢?

    我们可以找到比它的长度大的最小的Fibonacci数F(n),把它扩充成为一个长度为F(n)的数组,可以把它的最后一个元素补充到原数组后面,直到长度等于F(n)为止。

    例:

    在这里插入图片描述

    接下来,我们就可以计算mid值,进行分割数组了,具体步骤如下:

    斐波那契查找的基本步骤

    ①构建斐波那契数列;
    ②找出数组长度对应的斐波那契数列中的元素 F(n);
    ③如果数组长度小于斐波那契数列中对应的元素 F(n) 的值,则补充数组;
    ④确定查找点 mid = left+F(n-1)-1
    ⑤判断中间值 a[mid] 和目标值的关系:
    如果目标值小于中间值,说明目标值在左边。舍弃右边,对左边执行 4、5 两步(这时left=left,n=n-1);
    如果目标值大于中间值,说明目标值在右边。舍弃左边,对右边执行 4、5 两步(这时left=left+F(n-1),n=n-2);
    如果目标值等于中间值,说明找到了目标值。但此时还需判别该目标值是原数组中的元素还是补充的元素:
    如果是原数组中的元素,直接返回位置;
    如果是补充元素,则返回length-1;

    结束条件:数组不可再分。

    举例:数组:{1,2,4,8,9,15,27},查找元素8
    在这里插入图片描述

    代码实现:
    public static int fibonacciSearch(int[] arr, int findValue){
        int i = 0, mid,left = 0, right = arr.length-1; 
        int[] fibonacci = getFibonacci(20);
        while(fibonacci[i] < arr.length){
            i++;
        }
        int[] temp = Arrays.copyOf(arr, fibonacci[i]);
        for (int j=arr.length; j<temp.length; j++){
            temp[j] = arr[arr.length-1];
        }
        while (left <= right){
            mid = left + fibonacci[i-1]-1;  
            if (temp[mid] < findValue){ 
                left = mid + 1; 
                i -= 2;
            }else if (temp[mid] > findValue){    
                right = mid - 1;
                i -= 1;
            }else{ 
                if (mid <= right){  
                    return mid;
                }else{  
                    return right;
                }
            }
        }
        return -1;
    }
    public static int[] getFibonacci(int maxSize){
        int[] fibonacci = new int[maxSize];
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        for (int i=2; i<maxSize; i++){
            fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
        }
        return fibonacci;
    }
    

    代码来源:https://blog.csdn.net/zhuxian1277/article/details/112648982
    参考资料:https://blog.csdn.net/zhuxian1277/article/details/112648982

    展开全文
  • 斐波那契(黄金分割法)查找算法

    千次阅读 2021-01-15 10:28:48
    文章目录一、斐波那契查找算法概述1.1 什么是斐波那契查找算法1.2 什么是斐波那契数列1.3 斐波那契查找算法的思想二、斐波那契查找的基本步骤三、斐波那契查找的代码实现 一、斐波那契查找算法概述 1.1 什么是...

    一、斐波那契查找算法概述

    1.1 什么是斐波那契查找算法

    斐波那契搜索(Fibonacci search) ,又称斐波那契查找,是区间中单峰函数的搜索技术。斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。

    斐波那契查找同样是查找算法家族中的一员,它要求数据是有序的(升序或降序)。斐波那契查找采用和二分查找/插值查找相似的区间分割策略,都是通过不断的分割区间缩小搜索的范围

    1.2 什么是斐波那契数列

    要想具体学习斐波那契查找算法,就不得不先了解一下斐波那契数列。

    斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为 “兔子数列”。

    如下图所示,就是一个斐波那契数列:

    在这里插入图片描述

    在数学上,斐波那契数列被以如下递推的方法定义:
    F ( 0 ) = 0 ,   F ( 1 ) = 1 F(0) = 0, \ F(1) = 1 F(0)=0, F(1)=1

    F ( n ) = F ( n − 1 ) + F ( n − 2 ) ( n ≥ 2 , n ∈ N ∗ ) F(n) = F(n-1) + F(n-2) \qquad (n≥2,n∈N^*) F(n)=F(n1)+F(n2)(n2,nN)

    从斐波那契的递推公式我们可以总结出重要一点:斐波那契数列从第三项开始,每一项都等于前两项之和

    1.3 斐波那契查找算法的思想

    由 1.2 我们可以得知斐波那契数列的特点,而我们可以利用它的特点来做区间分割:可以将一个长度为 F(n) 的数组看作左右两段,左边一段长度是 F(n-1),右边一段长度是 F(n-2)。

    在这里插入图片描述

    正是上面这样的区间分割想法,使斐波那契数列和数组联系到了一起。这种分割思想亦是斐波那契查找算法的基础。

    斐波那契查找算法相对于二分查找和插值查找的基本思路是一致的,其中最重要的区别就是它们的查找点(或称中间值)的确定。斐波那契查找算法的查找点的计算公式如下
    m i d = l e f t + F ( n − 1 ) − 1 mid = left+F(n-1)-1 mid=left+F(n1)1
    【基本思想】

    完整的斐波那契查找的基本思想如下:在斐波那契数列找一个等于或第一个大于查找表中元素个数的数 F[n],然后将原查找表的长度扩展为 Fn (如果要补充元素,则重复补充原查找表最后一个元素,直到原查找表中满足 F[n] 个元素);扩展完成后进行斐波那契分割,即 F[n] 个元素分割为前半部分 F[n-1] 个元素,后半部分 F[n-2] 个元素;接着找出要查找的元素在哪一部分并递归,直到找到。

    二、斐波那契查找的基本步骤

    从上面我们知道了斐波那契查找算法的基本思想,根据它的基本思想,斐波那契查找的基本步骤可以分为以下几步:

    1. 构建斐波那契数列;
    2. 找出查找表长度对应的斐波那契数列中的元素 F(n);
    3. 如果查找表长度小于斐波那契数列中对应的元素 F(n) 的值,则补充查找表(以查找表最后一个元素补充);
    4. 根据斐波那契数列特点对查找表进行区间分隔,确定查找点 mid = left+F(n-1)-1(减 1 是因为数组下标从 0 开始);
    5. 判断中间值 arr[mid] 和目标值的关系,确定下一步策略:
      • 如果目标值小于中间值,说明目标值在左区间。由于左区间长度为 F(n-1),因此 n 应该更新为 n-1,然后再次执行 4、5 两步;
      • 如果目标值大于中间值,说明目标值在右区间。由于右区间长度为 F(n-2),因此 n 应该更新为 n-2,然后再次执行 4、5 两步;
      • 如果目标值等于中间值,说明找到了目标值。但此时还需判别该目标值是原查找表中的元素还是填充元素:
        • 如果是原查找表中的元素,直接返回索引;
        • 如果是填充元素,则返回原查找表的最后一个元素的索引,即 arr.length-1。(因为扩展数组是以原查找表最后一个元素来填充,如果目标值是填充元素,则说明原查找表最后一个元素值就是目标值)

    三、斐波那契查找的代码实现

    根据斐波那契查找算法的基本步骤,实现出的代码如下:

    /**
     * 斐波那契查找算法
     * @param arr   查找表
     * @param findValue 目标值
     * @return int  目标值在查找表中的索引
     */
    public static int fibonacciSearch(int[] arr, int findValue){
        int i = 0;
        int mid;    // 中间值
        int left = 0;   // 区间左端
        int right = arr.length-1;   // 区间右端
    
        // 1. 创建斐波那契数列
        int[] fibonacci = getFibonacci(20);
        // 2. 获取斐波那契数列中等于或者第一个大于数组长度的数
        while(fibonacci[i] < arr.length){
            i++;
        }
        // 3. 按照斐波那契数列中的元素长度拷贝一个查找表
        int[] temp = Arrays.copyOf(arr, fibonacci[i]);
        // 4. 以原查找表最后一个元素补齐临时查找表长度
        for (int j=arr.length; j<temp.length; j++){
            temp[j] = arr[arr.length-1];
        }
        // 5. 循环判断
        while (left <= right){
            mid = left + fibonacci[i-1]-1;  // 计算查找点
            if (temp[mid] < findValue){  // 如果查找点小于目标值,说明在右区间
                left = mid + 1; // 右区间起点
                i -= 2; // 右区间长度是 f[i-2],所以要把 i 换成 i-2
            }else if (temp[mid] > findValue){    // 如果查找点大于目标值,说明在左区间
                right = mid - 1; // 左区间终点
                i -= 1; // 左区间长度是 f[i-1],根据所以要把 i 换成 i-1
            }else{  // 如果相等,说明找到了
                /* 找到存在两种可能:一是找到的是原查找表中的元素,二是找到的是填充值。因此需要判别*/
                if (mid <= right){  // 如果是原查找表中的元素,直接返回索引
                    return mid;
                }else{  // 如果找到的是填充值,则返回原查找表最后一个索引
                    return right;
                }
            }
        }
        return -1;
    }
    
    /**
     * 创建斐波那契数列
     * @param maxSize   斐波那契数列长度
     * @return int[]    斐波那契数列
     */
    public static int[] getFibonacci(int maxSize){
        int[] fibonacci = new int[maxSize];
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        for (int i=2; i<maxSize; i++){
            fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
        }
        return fibonacci;
    }
    
    展开全文
  • 文章目录二分查找和差值查找概述实现斐波那契查找概述 二分查找和差值查找 二分查找和差值查找法基本一样,仅在一处代码不同,合并到一起描述 下面先讲二分查找 概述 二分查找也称折半查找(Binary Search),它是一...

    二分查找和差值查找

    二分查找和差值查找法基本一样,仅在一处代码不同,合并到一起描述

    下面先讲二分查找

    概述

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列
    百度百科: 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    实现

    二分查找方法前提是数列是有序的
    下面假设数列是从小到大排序
    思路: 用递归按照所寻找的数值与中间值的大小关系,对数列进行对半分,一直递归到所寻找的数值等于中间值或者数列中的元素给递归没了。
    进一步思路: 首先一个数列,我们找到数列中间的那个值,用此值和所要寻找的值进行大小比较。若此值更大,则取此值左边的数列再执行前面的操作(即找中间值再和所寻找的值比大小的操作)。若此值小,则取此值右边的数列进行再进行这样的操作。若两者相等,则表示找到了,则记录此中间值的索引,并从此索引向两边找一下看有没有相同的值(此时数列有序,可很简单的找到是不是有相同值)。若有,则也记录下这些值的索引然后返回这些索引的集合。若一直没找到,则当数列中没数据了,也结束循环,此时表示未找到
    大致思路: 写一个方法,作为递归的方法体,此方法接收四个参数,分别是:原数列(这里我们用数组)、每次递归所需要数列在数组中的起始点和终止点的索引值、要寻找的值。要两个点的索引值作用就是为了对数列进行中分,我们借由每次递归中,对两点索引传入值的不同来对数列进行对半分。起始终止两点决定了当前的递归是对数组中的那一部分数列进行操作。
    在方法体中,我们先获得当前数列的中间值的索引,然后获得中间值,然后用中间值和所要寻找的值进行大小比较。
    若中间值大,则进入下一次递归,下一次的递归传入的参数中,把终止位置的参数索引传入(中间值的索引+1),起始位置索引不变,其他参数也不变
    若中间值小,则进入下一次递归,下一次的递归传入的参数中,把起始位置的参数索引传入(中间值的索引+1),终止位置索引不变,其他参数也不变
    若两者相等,则表示找到此值在数列中的位置,记录下此中间值的索引,并从此索引向两边找一下看有没有相同的值(此时数列有序,可很简单的找到是不是有相同值)
    若有,则也记录下这些值的索引然后返回这些索引的集合。
    作为一个递归的方法体,我们得为递归进行考虑,所以在此方法体内,一开始,我们得先判断是否达到了递归结束的另一个条件,即是否此时递归中,起始位置是否大于终止位置,
    若大于则表示在此数组中未找到所要寻找的数据,直接返回一个空集合。这里需要知道几种情况,当起始位置等于终止位置,则表示此时数列中仅有一个数据,若大于,则表示一个数据也没了
    在这里插入图片描述
    上面是二分查找的主体代码
    二分查找和差值查找仅差了一点东西,即对中间值的取值更新上和退出递归的条件判断上
    int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
    百度百科: 插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。
    这里的自适应,指的就是他这个特殊的更新mid值的方法
    在插值查找中,mid的自适应公式是这样的:int mid=(left+right)/2;变为int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
    我也不知道这个公式从哪来的,但是确实可以加快查找速度
    在结束递归的条件判断上,需要更改一下:
    在这里插入图片描述
    多一个left=right,这是为了防止arr[right]-arr[left]=0导致的除0异常
    后面findVal<arr[0]||findVal>arr[arr.length-1],表示若寻找的数据大于数组最大的元素或者小于数组最小的元素,则直接返回,第一可以加快速度,而是也是最重要的一点,就是为了防止数组索引越界,因为所寻找的数据也参与了运算,防止所寻找的数据过大导致的mid过大,而使数组索引越界。

    不知道为什么,我在测试的时候,遇到过几次死递归的情况,就中间值的那个索引一直循环一段数字,或者干脆就直接是循环一个数字。

    全部代码:

    import java.util.ArrayList;
    import java.util.List;
    
    public class BinarySearch {
        public static void main(String[] args) {
            BinarySearchDemo searchDemo=new BinarySearchDemo();
            int[] array={1,2,3,4,5,6,7,8,9,10,11,12};
    
            int Array[]=new int[8000];
            for (int i = 0; i < 8000; i++) {
                Array[i]= (int) (Math.random()*8000);
            }
            QuickSortDemo sortDemo=new QuickSortDemo();
            sortDemo.SortDemo(Array);
    
            Long time1=System.currentTimeMillis();
    
            System.out.println(searchDemo.SearchDemo(Array, 452));
            System.out.println("耗时(毫秒)"+(System.currentTimeMillis()-time1));
    
        }
    }
    //二分查找方法前提是数列是有序的
    //下面假设数列是从小到大排序
    //思路:用递归按照所寻找的数值与中间值的大小关系,对数列进行对半分,一直递归到所寻找的数值等于中间值或者数列中的元素给递归没了
    //进一步思路:首先一个数列,我们找到数列中间的那个值,用此值和所要寻找的值进行大小比较,若此值更大,则取此值左边的数列再执行前面的操作(即找中间值再和所寻找的值比大小的操作)
    //若此值小,则取此值右边的数列进行再进行这样的操作,若两者相等,则表示找到了,则记录此中间值的索引,并从此索引向两边找一下看有没有相同的值(此时数列有序,可很简单的找到是不是有相同值)
    //若有,则也记录下这些值的索引然后返回这些索引的集合。若一直没找到,则当数列中没数据了,也结束循环,此时表示未找到
    //大致思路:写一个方法,作为递归的方法体,此方法接收四个参数,分别是:原数列(这里我们用数组)、每次递归所需要数列在数组中的起始点和终止点的索引值、要寻找的值
    //要两个点的索引值作用就是为了对数列进行中分,我们借由每次递归中,对两点索引传入值的不同来对数列进行对半分。起始终止两点决定了当前的递归是对数组中的那一部分数列进行操作
    //在方法体中,我们先获得当前数列的中间值的索引,然后获得中间值,然后用中间值和所要寻找的值进行大小比较,
    //若中间值大,则进入下一次递归,下一次的递归传入的参数中,把终止位置的参数索引传入(中间值的索引+1),起始位置索引不变,其他参数也不变
    //若中间值小,则进入下一次递归,下一次的递归传入的参数中,把起始位置的参数索引传入(中间值的索引+1),终止位置索引不变,其他参数也不变
    //若两者相等,则表示找到此值在数列中的位置,记录下此中间值的索引,并从此索引向两边找一下看有没有相同的值(此时数列有序,可很简单的找到是不是有相同值)
    // 若有,则也记录下这些值的索引然后返回这些索引的集合。
    //作为一个递归的方法体,我们得为递归进行考虑,所以在此方法体内,一开始,我们得先判断是否达到了递归结束的另一个条件,即是否此时递归中,起始位置是否大于终止位置,
    // 若大于则表示在此数组中未找到所要寻找的数据,直接返回一个空集合。这里需要知道几种情况,当起始位置等于终止位置,则表示此时数列中仅有一个数据,若大于,则表示一个数据也没了
    class BinarySearchDemo{
        public List SearchDemo(int[] arr,int findVal){
            return SearchDemo(arr,0, arr.length-1, findVal);
        }
        private List SearchDemo(int[] arr,int left,int right,int findVal){
            if (left>=right||findVal<arr[0]||findVal>arr[arr.length-1]){ //如果left>right,说明整个数列已经全部查找过了,而且没有找到,这里直接返回一个空集合
    //            这里需要再加一个=号,为了防止除0异常
                return new ArrayList<>();
    //            为什么进入这里就表示没找到呢?
    //            因为如果找到的话就会在后面那一部分代码中直接return,就不会有left>right的机会了
            }
    //        int mid=(left+right)/2;  //更新中间值的索引
            int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
            int midValue = arr[mid];
            if (findVal>midValue){
                //如果要找寻的值大于中间的那个值,则向右半部分寻找
                return SearchDemo(arr,mid+1,right,findVal);
            }else if (findVal<midValue){
                //如果要找寻的值小于中间的那个值,则向左半部分寻找
                return SearchDemo(arr,left,mid-1,findVal);
            }else{//            如果中间值正是寻找的值,则进入这里
                int i=mid; //先记录中间值的索引
                List<Integer> list=new ArrayList<>();  //放置所寻找的值在数列中可能有多个,这里创建一个集合,用来存储所有值的索引
                while ((i>=0)&&(arr[i]==findVal)){  //向找到的索引的左边寻找其他相同的值
                    list.add(i);
                    i--;
                }
                int n=mid+1;
                while ((n<arr.length)&&(arr[n]==findVal)){  //向找到的索引的右边寻找其他相同的值
                    list.add(n);
                    n++;
                }
                return list;
            }
        }
    }
    

    这里顺便测试了一下查找速度,QuickSortDemo sortDemo=new QuickSortDemo(); sortDemo.SortDemo(Array);是上一篇文章中写的快速排序

    斐波那契查找

    斐波那契查找我感觉是个很怪的东西,他又名黄金分割查找,顾名思义,其实斐波那契查找就是每次从黄金分割点对数列进行分割,其余的就跟二分查找一样,为啥非要在黄金分割点进行分割???我确实搞不明白,而且在测试的时候,我发现这个速度好像还更慢了
    在这个查找中,最重要的是如何找到黄金分割的那个点
    斐波那契数列其实是一个很奇妙的数列,这个数列越往后,数列的前一个的值与后一个值的比,就无限接近于黄金分割的那个值,即0.618… … 此处省略无限多位小数。
    借由这个特性,我们可以用斐波那契数列作为辅助,就可以很简单的找到数列的黄金分割点。所以,这个又叫斐波那契查找

    概述

    重要: 这个查找也必须建立在有序数列上

    百度百科: 斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n],将原查找表扩展为长度为F[n](如果要补充元素,则补充重复最后一个元素,直到满足F[n]个元素),完成后进行斐波那契分割,即F[n]个元素分割为前半部分F[n-1]个元素,后半部分F[n-2]个元素,找出要查找的元素在那一部分并递归,直到找到。
    简单来说:
    首先,这个查找的方法也是一种二分查找,不过他不是中分,数列的起始位置到分割点间元素的个数,比上整个数列元素的个数接近于黄金分割的那个数值,按照这样的方式来分割,来找分割点,由于斐波那契数列的特性,可以利用斐波那契数列中的值来寻找分割点,即先找到斐波那契数列中的一个值,要求此值(即为F[n])大于或等于而且最接近数列中元素的个数,若F[n]大于数列中元素的个数,则将原数列扩充到长度为F[n],扩充的位置用0来填充。
    然后由于斐波那契数列F[n]=F[n-1]+F[n-2],而且,F[n-1]/F[n]无限接近与0.618即黄金分割值
    所以F[n-1]-1即为F[n]数列的分割点的索引。为什么要-1?因为F[n-1]表示的是一个长度,他从1开始,索引是从0开始
    有因为F[n-2]是F[n-1]前面的那个值,所以F[n-1]数列的分割点就是F[n-2]-1
    以此类推
    但是注意一点: 我们是在一个数组中进行操作的,每次需要查找的那段数列的起始位置的索引不一定是0,索引每次的分割点其实是起始位置索引+F[n-1]-1

    实现

    实现思路: 首先写一个函数用于创建一个斐波那契数列,用于后续的使用
    然后再写一个方法体,即实现斐波那契查找的方法体,首先,用循环找到不小于且最接近数列长度的那个斐波那契数列的值,然后用循环把原数列扩充到对应的大小
    然后正式开始查找,用while循环,循环结束条件是数列中没有数据了即起始位置大于终止位置的时候,或者找到了结果的时候
    首先找到分割点,然后判断分割点元素的大小和所寻找数据的大小关系
    若分割点更大,则向分割后左边部分的数列寻找,并更新所需斐波那契数值的索引(用于后续的寻找分割点)。怎么更新具体在下面代码的注释中
    若分割点更小,则向分割点右边部分的数列寻找,并更新所需斐波那契数值的索引(用于后续的寻找分割点)。怎么更新具体在下面代码的注释中
    代码如下:

    import java.util.Arrays;
    
    public class FibonacciSearch {
        public static void main(String[] args) {
            FibonacciSearchDemo searchDemo=new FibonacciSearchDemo();
            int[] array={0,1,3,5,7,8,9,10,11,12,45,78,49};
            int Array[]=new int[8000000];
            for (int i = 0; i < 8000000; i++) {
                Array[i]= (int) (Math.random()*8000000);
            }
            QuickSortDemo sortDemo=new QuickSortDemo();
            sortDemo.SortDemo(Array);
    
            Long time1=System.currentTimeMillis();
            System.out.println(searchDemo.SearchDemo(Array, 12));
            System.out.println("耗时(毫秒)"+(System.currentTimeMillis()-time1));
    
        }
    }
    class FibonacciSearchDemo{
        public int SearchDemo(int[] arr,int key){
            int low=0;  //记录数列的起始索引
            int high= arr.length-1;   //记录数列的终止索引
            int[] fib=getFibArr(100);  //接收斐波那契数列
            int k=0;//用来记录所需的斐波那契数值在斐波那契数列中的索引
            int mid;//mid用来记录数列中的中分点
    
    //        在斐波那契数列中寻找一个数值,要求此值不小于数列的长度,且最接近数列的长度
            while (high+1>fib[k]-1){  //为什么要加一?因为hight表示的是最大索引值,他和数列的长度差1
    //            为什么fib[k]-1,因为我们要找到那个值不小于数列的长度,而且,是最接近数列的长度的那个值
                k++;
            }
    
    //        数列的原长度可能达不到前面找到的那个数值的大小,这里需要将数列扩增
            int[] temp= Arrays.copyOf(arr,fib[k]);//这个方法可以将arr数组增长到fib[k],增加的元素都默认为0
    //        我们需要的是用数列的最后一个元素来填充数组,所以需要修改后面的0
            for (int i = high+1; i < temp.length; i++) {
                temp[i]=arr[high];
            }
    
            while (low<=high){
                mid=low+fib[k-1]-1;//为啥最后面要减一?因为fib[k-1]在此处表示的是一个数量,即从low索引到中分点间的元素个数,而此处我们想要的mid表示的是一个索引
    //            这里为啥是fib[k-1]?因为fib[k]表示的是这个数列的长度,所以这个数列的黄金分割点到数列头的长度就是fib[k]的前一个数值,我们这里需要的就是黄金分割点,所以k-1
                if (key<temp[mid]){  //若所寻找的值小于中间值,则进入分割后左边的数列,即F[k-1]的那一部分数列
                    high=mid-1;
                    k--;
    //                为什么这里k自减?因为进入下次循环的时候,从数列头到这个黄金分割点(即f[k-1])的长度,就是我们下次循环时候数列的总长,
    //                而这个数列的黄金分割点正是f[k-1]的前一个数值,所以这里我们需要得到的是斐波那契数列中的前一个数值,即fib[k-1]的前一个数值,所以是k--
                }else if (key>temp[mid]){   //若所寻找的值大于中间值,则进入分割后右边的那一部分数列,即F[k-2]的那一部分
                    low=mid+1;
                    k-=2;
    //                这里为什么是k自减2?因为当数列经过黄金分割之后,如果key>temp[mid],即key在经过黄金分割后的数列的后半部分,
    //                则我们下次就需要把后半部分的这个数列进行黄金分割找值,如果要对这个数列黄金分割,我们需要先知道这个数列的长度,这个数列的长度就很明显
    //                因为斐波那契数列f(n)=f(n-1)+f(n-2),由因为黄金分割后数列后半部分长度不可能大于前半部分长度,所以后半部分长度就是f(n-2)了,
    //                f(n-2)的黄金分割点就是这次黄金分割点的上上个数值,即f[k-1]的上上个数值,也就是f[k-1-1-1],所以f[k-1-1]的黄金分割点又是f[k-1-1]的上一个数值
    //                所以此处是k自减2
    //                明明后面是个减三个1为啥这里只k自减两次?因为,在每次循环开始之前,得到的中间值都是low+fib[k-1]-1,每次用的值不是k而是k-1
                }else {
                    return mid;
                }
            }
            return -1;
        }
        public int[] getFibArr(int n){
            int[] fib=new int[n];
            fib[0]=0;
            if (n==1){
                return fib;
            }
            fib[1]=1;
            if (n==2){
                return fib;
            }
            for (int i = 2; i < n; i++) {
                fib[i]=fib[i-1]+fib[i-2];
            }
            return fib;
        }
    }
    

    这里顺便测试了一下在8百万个数据中查找的速度,QuickSortDemo sortDemo=new QuickSortDemo(); sortDemo.SortDemo(Array);是上一篇文章中写的快速排序

    展开全文
  • 斐波那契查找算法

    2019-09-16 10:48:48
    斐波那契查找算法(黄金分割查找算法): mid = low + F(k-1) - 1; F代表斐波那契数列 对于F(k-1)-1的理解:由斐波那契数列 F[k] = F[k-1]+F[k-2] 的性质,可以得到 F[k-1] = F[k-1] -1+F[k-2] -1+1 ...
  • \quad \quad在介绍斐波那契查找算法之前,先介绍一下很它紧密相连的一个概念——黄金分割。黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大...
  • 同系列算法问题 回溯法解决流水作业调度问题(全排列+计算模型+剪枝函数) 回溯法解决N皇后问题-Python实现(全排列+剪枝) 贪心算法解决活动安排-Python实现(排序+贪心选择) 问题 问题概述 分析问题 ...
  • 算法 - 查找 - 斐波那契查找 (Fibonacci Search)

    万次阅读 多人点赞 2019-05-15 17:08:34
    斐波那契查找 (Fibonacci Search)
  • 斐波那契查找算法解析

    千次阅读 2021-11-12 17:53:46
    文章目录前言一、斐波那契数列二、斐波那契查找算法 前言 学数据结构的时候被斐波那契查找算法困扰,刚开始难以理解,脑袋有点懵,翻看了许多大佬的博文,加上自己的理解发了出来 一、斐波那契数列 我们先看什么是...
  • 1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找 2)将折半查找中的求mid 索引的公式, low表示左边索引, high表示右边索引. 3)int midindex =low + (high-low) * (key - arr(low) / ...
  • ​ 谈到斐波那契查找算法,总是有一个神奇的数字与之紧密相连——黄金分割数(0.618)。黄金分割数被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在...
  • 斐波那契查找Fibonacci Search)也是有序表的一种查找方式,同样属于二分查找的一个优化,它是利用了黄金分割原理(斐波那契数列)来实现的。改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金...
  • 斐波那契查找算法:前提是一个有序数组。 斐波那契数列:1,1,2,3,5,8,13,21。。。。。。 主要思想:通过斐波那契数列找到数组黄金分割点附近的下标,即mid。 根据上图所示:假设有一个数组,数组里面的元素有F[k]-1...
  • 一、基本介绍 1.黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位 数字的近似值是 0.618。...斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置
  • 摘要:VC/C++源码,算法相关,插值查找 C++二分查找、插值查找斐波那契查找对比C++的实现源码,不是完整程序,仅是核心算法文件,需要完整功能估计自己得动动手啦。
  • 一、斐波那契查找算法介绍 斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1...
  • 斐波那契查找算法介绍斐波那契查找法肯定与斐波那契相关嘛,斐波那契数列 又称黄金分割数列。所以我们先把黄金分割弄懂,后面代码才能看得懂!黄金分割点大家都知道吧。1:0.618或者1.618:1,我们的斐波那契数列越...
  • Java斐波那契查找算法 package myfirstprogram; import java.util.Arrays; public class Fibonacci_Search { //因为java没有斐波那契数列的引用方法,所以得构造数列 public static int[] fib(int n) { int[] ...
  • 铺垫知识: 黄金分割点: 黄金分割点是指把一条线段(长度为H)分割成两部分A和B,...斐波那契数列: {1,1,2,3,5,8,13,21,34,55...}这个数列满足如下性质: 1、index为0和1的元素的值都为1; 2、从第三个元素开...
  • package cn.mrlij.search; import java.util.Arrays; public class FibonacciSearch { public static int maxSize = 20; public static void main(String[] args) { int arr[] = {2,3,6,8,9,20};...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,985
精华内容 7,194
关键字:

斐波那契查找算法

友情链接: cElectronicAlbum.rar