您现在的位置是:首页 > 正文

【数据结构与算法】插值查找算法、斐波那契查找算法(黄金分割法)的介绍和程序实现

2024-01-30 19:35:58阅读 0

1. 插值查找算法

1.1 插值查找算法的介绍

插值查找算法类似二分查找算法。二分查找算法的mid取值为 m i d = l o w + h i g h 2 = l o w + 1 2 ( h i g h − l o w ) mid =\cfrac{low + high}{2} = low + \cfrac{1}{2}(high -low) mid=2low+high=low+21(highlow)

而插值查找算法,并不是取low和high中间的index,而是根据findValue的值的大小来确定mid,findValue值偏大,则mid偏大,findValue值偏小,则mid偏小,这样能缩小查找的范围。mid取值公式为 m i d = l o w + f i n d V a l u e − a r r a y [ l o w ] a r r a y [ h i g h ] − a r r a y [ l o w ] ( h i g h − l o w ) mid = low + \cfrac{findValue - array[low]}{array[high] - array[low]}(high - low) mid=low+array[high]array[low]findValuearray[low](highlow)

插值查找注意事项:对于数据量较大,数值分布比较均匀的有序序列来说,采用插值查找速度较快。数值分布不均匀的情况下,该方法不一定比二分查找好

1.2 插值查找算法的程序实现

需求:在一个有序数组{1, 2, 3, …, 98, 99, 100}中,用插值查找算法查找一个数在该数组的index,查找不到则返回-1

程序如下:

public class InsertValueSearch {

    public static void main(String[] args) {

        // 构建一个均匀的有序数组
        int[] array = new int[100];
        for (int i = 0; i < 100; i++) {
            array[i] = i + 1;
        }

        // 进行插值查找
        int findValueIndex = insertValueSearch(array, 0, array.length - 1, 100);
        if (findValueIndex == -1) {
            System.out.println("未找到");
        } else {
            System.out.printf("找到的值的下标是: %d\n", findValueIndex);
        }
    }
    
    /* 参数含义如下:
    low: 此次查找的最小数组下标
    high: 此次查询的最大数组下标
     */
    public static int insertValueSearch(int[] array, int low, int high, int findValue) {
        // 因为findValue参与到mid的取值,所以需要先限制findValue < array[0] || findValue > array[array.length - 1]
        // 否则求出来的mid会越界

        // 当low > high表示未找到,返回-1
        if (low > high || findValue < array[0] || findValue > array[array.length - 1]) {
            return -1;
        }

        // 根据findValue的取值,求和合适的mid值
        int mid = low + (findValue - array[low]) / (array[high] - array[low]) * (high - low);
        int midValue = array[mid];
        if (findValue > midValue) {
            // 向找到的值右边,遍历查找相同值
            return insertValueSearch(array, mid + 1, high, findValue);
        } else if (findValue < midValue) {
            // 向找到的值左边,遍历查找相同值
            return insertValueSearch(array, low, mid - 1, findValue);
        } else {
            // 如果和midValue相同,则表示找到
            return mid;
        }

    }
}

运行程序,结果如下:

找到的值的下标是: 99

2. 斐波那契查找算法

2.1 斐波那契查找算法的介绍

黄金分割点是指把一条线段分割为AB两部分,使A部分与全长之比约等于0.618,而把A部分继续分割为CD两部分,使C部分与A部分之比约等于0.618,然后按照此方法循环分割

可以借助斐波那契数列来方便的进行黄金分割点的查找。斐波那契数列:{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …, F[k] = F[k-1] + F[k - 2]},第一个数和第二个数为1,从第三个数开始,值为前两个数的和。而相邻的两个数之比约等于0.618

而斐波那契查找算法和二分查找算法、插值插值算法类似,只是mid得确认方法不同。斐波那契查找算法的mid就是数组index的黄金分割点,而构造一个斐波那契数列,其各个值就对应要查找的数组的多个index,就可以很方便的找到mid

index的斐波那契构建求mid:因为mid位于黄金分割点,且会占用一个位置,为了便于下一次分割。所以F[k-1]-1 + 1 + F[k-2]-1 = F[k]-1,mid = low + F[k-1]-1,需要构建的数组buildArray长度 - 1为F[k]-1。确定一个合适的k,让查找的数组array的长度 - 1小于等于F[k]-1,buildArray的前面部分的值用array的值填充,后面的部分的值用array[high]填充,构建完的buildArray的index就可以方便的查找黄金分割点

2.2 斐波那契查找算法的程序实现

需求:在一个有序数组{1,8, 10, 89, 1000, 1234}中,用斐波那契查找算法查找一个数在该数组的index,查找不到则返回-1

程序如下:

import java.util.Arrays;

public class FibonacciSearch {

    public static void main(String[] args) {
        int[] array = {1, 8, 10, 89, 1000, 1234};

        // 进行斐波那契查找
        int arrayIndex = fibonacciSearch(array, 89);
        if (arrayIndex == -1) {
            System.out.println("未找到");
        } else {
            System.out.printf("找到的值的下标是: %d\n", arrayIndex);
        }
    }

    // 进行斐波那契数列的构建,即{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ......, F[k] = F[k-1] + F[k - 2]}
    // 因为我们测试的原始数组array长度很小,这里斐波那契数组的长度为10就可以了
    public static int[] getFibonacciArray() {
        int fibonacciArraySize = 10;
        int[] fibonacciArray = new int[fibonacciArraySize];
        fibonacciArray[0] = 1;
        fibonacciArray[1] = 1;
        for (int i = 2; i < fibonacciArraySize; i++) {
            fibonacciArray[i] = fibonacciArray[i - 1] + fibonacciArray[i - 2];
        }
        return fibonacciArray;
    }

    // 斐波那契查找算法实现
    public static int fibonacciSearch(int[] array, int findValue) {
        int low = 0;
        int high = array.length - 1;
        int[] fibonacciArray = getFibonacciArray();
        // 斐波那契数组的index
        int k = 0;
        int mid;

        // 确定一个合适的k,让查找的数组array的长度 - 1小于等于F[k]-1
        // 所以构建的数组buildArray的长度为F[k]
        while (high > fibonacciArray[k] - 1) {
            k++;
        }

        // 构建的数组buildArray,buildArray的前面部分的值用array的值填充,后面的部分的值默认用0填充
        int[] buildArray = Arrays.copyOf(array, fibonacciArray[k]);

        // 再将后面的部分的值用array[high]填充
        for (int i = high + 1; i < buildArray.length; i++) {
            buildArray[i] = array[high];
        }

        // 如果low > high则表示未找到,返回-1
        while (low <= high) {
            // 求出黄金分割点mid
            mid = low + fibonacciArray[k - 1] - 1;
            // 如果比黄金分割点值小,则继续对前面一部分进行黄金分割点查找
            if (findValue < buildArray[mid]) {
                high = mid - 1;
                // 比黄金分割点值小,则这一部分是0.618那部分,即F[k-1] - 1那一部分
                // 所以k -= 1,然后再对这一部分继续进行黄金分割点查找
                k--;
                // 如果比黄金分割点值大,则继续对后一部分进行黄金分割点查找
            } else if (findValue > buildArray[mid]) {
                low = mid + 1;
                // 比黄金分割点值大,则这一部分是0.382那部分,即F[k-2] - 1那一部分
                // 所以k -= 2,然后再对这一部分继续进行黄金分割点查找
                k -= 2;
            } else {
                // 否则表示找到

                // 如果mid比high小,直接返回mid
                if (mid <= high) {
                    return mid;
                } else {
                    // 因为填充可能会导致mid比high大,如果mid比high大,则返回high
                    return high;
                }
            }
        }
        return -1;
    }
}

运行程序,结果如下:

找到的值的下标是: 3

网站文章

  • Mac帆软生成docker镜像

    Mac帆软生成docker镜像

    2024-01-30 19:35:53
  • CentOS7安装MySQL

    CentOS7安装MySQL

    MySQL的下载地址:https://dev.mysql.com/downloads/mysql/1.由于企业版的要收费,这里就下载社区版的MySQL1-1.按红圈的下载2.下载完成后,上传到服务器[root@node1 ~]# rz #上传文件[root@node1 ~]# ls ...

    2024-01-30 19:35:26
  • Set对象

    Set对象

    https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects 可查看网站 Set对象允许你存储任何类型的唯一值,无论是原始值或者是对象引用。 set对象中有很多的方法 1、Set.prototype.add() add()方法用来向一个Set对象的末尾添加一个指定的值。 var...

    2024-01-30 19:35:20
  • APK调试

    APK调试

    源码的情况下,对APK的动态调试主要分为两种:smali汇编动态调试arm汇编动态调试Smali汇编动态调试对smali汇编的动态调试主要分为两种:使用ida进行调试使用IDE + apktool进行调试Eclipse + apktoolAndroid studio + apktoolIdea + apktool…使用jeb2.2以后版本调试IDA 调试smali...

    2024-01-30 19:35:13
  • 使用SourceMonitor完成静态测试

    使用SourceMonitor完成静态测试

    摘要:软件测试作为软件开发中的重要环节,其重要程度不言而喻,从需求定制到软件交付,不仅要保证软件在功能上的要求,同时也要满足性能需求。毕竟,客户体验才是软件赖以生存的基石。本篇文章主要讲述了如何使用SourceMonitor这款软件完成最基本的静态测试,整个流程比较简单。一、软件安装由于本次实验是基于SourceMonitor这款软件完成的,所以需要先下载相应的安装包,网上搜...

    2024-01-30 19:35:05
  • 南艺附中 计算机音乐,南京艺术学院2018年音乐类本科招生考试科目及内容

    南京艺术学院2018年音乐类本科招生考试科目及内容考试科目及内容招生专业及方向考试科目、内容音乐表演(声乐演唱)初试:①演唱(自选歌曲1首)②面试复试:①演唱(自选歌曲2首,曲目不同于初试)②基本乐理...

    2024-01-30 19:34:38
  • Toad for Oracle工具的使用(二)

    Toad for Oracle工具的使用(二)

    脚本管理器 (Script manager): 通过Script Manager,可以对常用的SQL 脚本进行集中管理。还可以做如下工作:

    2024-01-30 19:34:30
  • 翻转棋

    翻转棋

    广搜的问题,重点是位运算的应用。每翻转一个状态就对应一个16位的二进制数。翻转一次就是把某个数上下左右四个位置的棋子都翻转,即0-&gt;1,1-&gt;0。 Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26891 Accepted: 11647

    2024-01-30 19:34:22
  • Linux下Shell实现当文件大于某size时候删除功能

    Linux下Shell实现当文件大于某size时候删除功能

    2024-01-30 19:33:50
  • c++实现八数码游戏

    c++实现八数码游戏 #include #include #include #include #include #include #include #include #include #include #in

    2024-01-30 19:33:43