二分查找的一种改进-拉格朗日插值查找法

标签: 编程语言

引言

二分查找算法是比较早期时候接触到的算法,这种算法有两个要求,一个是要求是顺序存储结构,其实就是数组,另一个是要查找的表要按照大小有序排列。

代码讨论

轻量级查找

我们先看下最基础的查找,基本思想就是从一个数组上面挨个找,找到了就返回:

 public static int find_v1(int[] arr, int targetValue) {
        int targetIndex = -1;
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            times++;
            if (arr[i] == targetValue) {
                targetIndex = i;
                break;
            }
        }

        if (targetIndex != -1) {
            System.out.println("find_v1找到目标值下标:arr[" + targetIndex + "]=" + targetValue + ",查找次数为:" + times);
        } else {
            System.out.println("find_v1没有找到值");
        }
        return targetIndex;
    }

二分法的引入

二分法的思想是把数据一分为二,因为数组上面的数据其实是有序的,所以可以提前判断要找的目标数据是在前半段还是后半段:

public static int find_v2(int[] arr, int targetValue) {
        int targetIndex = -1;
        int times = 0;
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            times++;
            int mid = low+(high - low) / 2;
            if (arr[mid] == targetValue) {
                targetIndex = mid;
                break;
            } else if(targetValue > arr[mid]){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        if (targetIndex != -1) {
            System.out.println("find_v2找到目标值下标:arr[" + targetIndex + "]=" + targetValue + ",查找次数为:" + times);
        } else {
            System.out.println("find_v2没有找到值");
        }
        return targetIndex;
    }

二分查找中的核心就是 int mid = low+(high - low) / 2,low我们可以理解为下界,high是我们查找范围的上界,自然来说high-low其实是我们查找的范围,画图表示其实就是:
在这里插入图片描述
我们其实可以把mid表示为mid=low+(high - low) *1/2,在这里1/2只是一个比率,我们其实可以看到目标数据在靠后一点点,不在中间范围内。我们其实可以进一步考虑,这个切割的时候靠中间往后切一点是不是比较合适,更加极端的,我们假如就是237,500的地方,是不是比率直接变成0.8会比较合适。
在这里插入图片描述
这个便是我们改进算法的思想,我们求出这个分布的比率,可以进一步缩小查找的范围,关键代码如下,我们是求目标值与全局查找的范围求得我们数据的比率:

double rate=(targetValue-arr[low])*1.0/(arr[high]-arr[low]);
int mid = (int)(low+(high - low)* rate);

完整代码如下:

  public static int find_v3(int[] arr, int targetValue) {
        int targetIndex = -1;
        int times = 0;
        int low = 0;
        int high = arr.length - 1;
        while (low < high) {
            times++;
            double rate=(targetValue-arr[low])*1.0/(arr[high]-arr[low]);
            System.out.printf("rate:%.20f\n",rate);
            int mid = (int)(low+(high - low)* rate);
            System.out.println("high="+high+" low="+low+" mid="+mid);
            if (arr[mid] == targetValue) {
                targetIndex = mid;
                break;
            } else if(targetValue > arr[mid]){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }

        if (targetIndex != -1) {
            System.out.println("find_v3找到目标值下标:arr[" + targetIndex + "]=" + targetValue + ",查找次数为:" + times);
        } else {
            System.out.println("find_v3没有找到值");
        }
        return targetIndex;
    }

三种情况测试对比:

public static void main(String[] args) {
        int[] array = {1, 3, 4, 6, 7, 89, 234, 235, 236, 237, 500, 501, 502, 503, 504};
        System.out.println(Arrays.toString(array));
        System.out.printf("rate:%.20f\n",501*1.0/502);
        searchAll(array,501);
        searchAll(array,502);
        searchAll(array,89);
        searchAll(array,7);

    }

    public static void searchAll(int[] array,int targetValue){
        System.out.println("searchAll begin...");
        find_v1(array, targetValue);
        find_v2(array, targetValue);
        find_v3(array, targetValue);
        System.out.println("searchAll end...");

    }
[1, 3, 4, 6, 7, 89, 234, 235, 236, 237, 500, 501, 502, 503, 504]
rate:0.99800796812749000000
searchAll begin...
find_v1找到目标值下标:arr[11]=501,查找次数为:12
find_v2找到目标值下标:arr[11]=501,查找次数为:2
rate:0.99403578528827040000
high=14 low=0 mid=13
rate:0.99800399201596800000
high=12 low=0 mid=11
find_v3找到目标值下标:arr[11]=501,查找次数为:2
searchAll end...
searchAll begin...
find_v1找到目标值下标:arr[12]=502,查找次数为:13
find_v2找到目标值下标:arr[12]=502,查找次数为:4
rate:0.99602385685884690000
high=14 low=0 mid=13
rate:1.00000000000000000000
high=12 low=0 mid=12
find_v3找到目标值下标:arr[12]=502,查找次数为:2
searchAll end...
searchAll begin...
find_v1找到目标值下标:arr[5]=89,查找次数为:6
find_v2找到目标值下标:arr[5]=89,查找次数为:3
rate:0.17495029821073560000
high=14 low=0 mid=2
rate:0.16666666666666666000
high=14 low=3 mid=4
rate:0.00000000000000000000
high=14 low=5 mid=5
find_v3找到目标值下标:arr[5]=89,查找次数为:3
searchAll end...
searchAll begin...
find_v1找到目标值下标:arr[4]=7,查找次数为:5
find_v2找到目标值下标:arr[4]=7,查找次数为:4
rate:0.01192842942345924400
high=14 low=0 mid=0
rate:0.00798403193612774400
high=14 low=1 mid=1
rate:0.00600000000000000000
high=14 low=2 mid=2
rate:0.00200803212851405600
high=14 low=3 mid=3
rate:0.00000000000000000000
high=14 low=4 mid=4
find_v3找到目标值下标:arr[4]=7,查找次数为:5
searchAll end...

版权声明:本文为zhuxuemin1991原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/zhuxuemin1991/article/details/104108978

智能推荐

Qt 之 Query Model Example 解析

总体概括 Query Model Example主要演示了怎么使用QSqlQueryModel这个数据库查询模型类。其中包括创建普通的数据库查询模型、可编辑的数据库查询模型和自定义的数据库查询模型。普通(默认)的数据库查询模型是只读的(不可再模型中编辑数据,模型只通过视图展示数据);可编辑的数据库查询模型重写了QSqlQueryModel的flags()方法和setData()方法;自定义的数据库...

Flutter:Scaffold.of() called with a context that does not contain a Scaffold.

Flutter:Scaffold.of() called with a context that does not contain a Scaffold. 当我第一次点击按钮想要弹出底部消息时出现了如下错误 当BuildContext在Scaffold之前时,调用Scaffold.of(context)会报错。这时可以通过Builder Widget来解决,代码如下:...

【机器学习基础】线性回归

                                                        &nbs...

08-Vue实现书籍购物车案例

书籍购物车案例 index.html main.js style.css 1.内容讲解 写一个table和thead,tbody中每一个tr都用来遍历data变量中的books列表。 结果如下: 在thead中加上购买数量和操作,并在对应的tbody中加入对应的按钮。结果如下: 为每个+和-按钮添加事件,将index作为参数传入,并判断当数量为1时,按钮-不可点击。 结果如下: 为每个移除按钮添加...

堆排序

堆排序就是利用堆进行排序的方法,基本思想是,将代排序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换,此时末尾元素就是最大值,移除末尾元素,然后将剩余n-1个元素重新构造成一个大根堆,堆顶元素为次大元素,再次与末尾元素交换,再移除,如此反复进行,便得到一个有序序列。 (大根堆为每一个父节点都大于两个子节点的堆) 上面思想的实现还要解决两个问题: 1.如何由一个无...

猜你喜欢

基础知识(变量类型和计算)

一、值类型 常见的有:number、string、Boolean、undefined、Symbol 二、引用类型 常用的有:object、Array、null(指针指向为空)、function 两者的区别: 值类型暂用空间小,所以存放在栈中,赋值时互不干扰,所以b还是100 引用类型暂用空间大,所以存放在堆中,赋值的时候b是引用了和a一样的内存地址,所以a改变了b也跟着改变,b和a相等 如图: 值...

Codeforces 1342 C. Yet Another Counting Problem(找规律)

题意: [l,r][l,r][l,r] 范围内多少个数满足 (x%b)%a!=(x%a)%b(x \% b) \% a != (x \% a) \% b(x%b)%a!=(x%a)%b。 一般这种题没什么思路就打表找一下规律。 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 29 30 31 32 33 34 35 36 37 38 39 40 41 49 50...

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3)

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3) (Credit: https://gitee.com/paddlepaddle/Paddle/raw/develop/doc/imgs/logo.png) MNIST数据集 MNIST数据集可以认为是学习机器学习的“hello world”。最早出现在1998年LeC...

哈希数据结构和代码实现

主要结构体: 实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构 完整代码参见github: https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash...