算法|1.二分及其扩展

算法|1.二分及其扩展

1、有序数组中找到num

题意：给定有序数组，在有序数组中找到指定数字，找到返回true，找不到返回false.

解题思路：

  • 数组有序查找指定元素使用二分法
  • L指针初始值设为0，R指针初始值设为arr.length-1，属于左闭右闭的区间，循环条件为L<=R

优化的点：

  • 求平均值使用有符号右移：mid=left+((right-left)>>1).好处有两点1.防止溢出2.提高效率

对数器：

  • 使用顺序遍历
  • 前提：生成随机数组

核心代码：

public static boolean exist(int[] arr,int num){
    int L=0;
    int R=arr.length-1;
    int M=L+((R-L)>>1);
    while(L<=R){
        if(arr[M]<num){
            L=M+1;
        }else if(arr[M]>num){
            R=M-1;
        }else{
            return true;
        }
        M=L+((R-L)>>1);
    }
    return false;
}

测试代码：

    //for test
    public static boolean test(int[] arr,int num){
        for (int cur:arr) {
            if(cur==num){
                return true;
            }
        }
        return false;
    }
    //for test
    public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr=new int[(int) ((maxSize+1)*Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
        }
        return arr;
    }

    //for test
    public static void print(int[] arr){
        for (int cur:arr) {
            System.out.print(cur+" ");
        }
        System.out.println();
    }
//    //for test
    public static void main(String[] args) {
        int testTime=1000;
        int maxSize=10;
        int maxValue=100;
        boolean succeed=true;
        for (int i = 0; i < testTime; i++) {
            int[] arr=generateRandomArray(maxSize,maxValue);
            int num=(int) ((maxValue+1)*Math.random());

            //使用前提：数组是有序的
            Arrays.sort(arr);

            boolean ret1=exist(arr,num);
            boolean ret2=test(arr,num);
            if(ret1!=ret2){
                print(arr);
                System.out.println("num:"+num);
                System.out.println("exist:"+ret1);
                System.out.println("test:"+ret2);
                System.out.println("Oops!Error!");
                succeed=false;
                break;
            }
        }
        if(succeed==true){
            System.out.println("succeed!");
        }
    }

测试结果：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0HyhetxX-1685076234668)(F:\typora插图\image-20230526103704932.png)]

果然，人长时间不写代码，脑子是会秀逗的（…）

你敢信这是一开始写的？？真该死啊…

public static boolean exist(int[] arr,int num){
    int L=0;
    int R=arr.length-1;
    int M=L+((R-L)>>1);
    while(L<=R){
        if(arr[L]<num){
            L=M+1;
        }else if(arr[R]>num){
            R=M-1;
        }else{
            return true;
        }
        M=L+((R-L)>>1);
    }
    return false;
}

还debug半天反应不过来

    //for test
    //1.使用前提：必须是有序的
    //2.sort排序不生效——得是M和Num比啊！！！
//    public static void main(String[] args) {
//        int[] arr={-15, -14 ,4 ,24, 26, 33, 81  };
//        Arrays.sort(arr);
//        if(exist(arr,4)!=test(arr,4)){
//            System.out.println(false);
//        }else{
//            System.out.println(true);
//
//        }
//    }

2、有序数组中找到>=num的最左边的位置

题意：给定有序数组，在有序数组中找到>=指定数字的最左边的下标，找到返回对应值，找不到返回-1.

解题思路：

  • 注意：这里并没有要求value值必须存在于指定数组
  • 数组有序查找指定元素下标使用二分法
  • 在原来的基础上增加一个变量记录当前查找元素下标，如果当前值大于等于指定值，则记录下标。最终返回的结果只可能是两种值-1，符合题意的值

优化思路：

  • 没有采用在上一题的基础上增加变量记录当前坐标，然后再对这个坐标进行操作，而是直接在分支条件上动手，记录并迭代更新，这样只需要在返回处进行判断是否存在这样的值即可。

对数器：

  • 顺序遍历

核心代码：

public static int nearestIndex(int[] arr,int num){
    int L=0;
    int R=arr.length-1;
    int M=L+((R-L)>>1);
    int index=-1;
    while(L<=R){
        if(arr[M]>=num){
            index=M;
            R=M-1;
        }else{
            L=M+1;
        }
        M=L+((R-L)>>1);
    }
    return index;
}

测试代码：

基本同上，但是需要修改比对方法和核心方法的返回值

//for test
public static int test(int[] arr,int num){
    for (int i = 0; i < arr.length; i++) {
        if(arr[i]>=num){
            return i;
        }
    }
    return -1;
}
//for test
public static int[] generateRandomArray(int maxSize,int maxValue){
    int[] arr=new int[(int) ((maxSize+1)*Math.random())];
    for (int i = 0; i < arr.length; i++) {
        arr[i]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
    }
    return arr;
}

//for test
public static void printArray(int[] arr){
    for (int cur:arr) {
        System.out.print(cur+" ");
    }
    System.out.println();
}
//    //for test
public static void main(String[] args) {
    int testTime=1000;
    int maxSize=10;
    int maxValue=100;
    boolean succeed=true;
    for (int i = 0; i < testTime; i++) {
        int[] arr=generateRandomArray(maxSize,maxValue);
        int num=(int) ((maxValue+1)*Math.random());

        //使用前提：数组是有序的
        Arrays.sort(arr);

        int ret1=nearestIndex(arr,num);
        int ret2=test(arr,num);
        if(ret1!=ret2){
            printArray(arr);
            System.out.println("num:"+num);
            System.out.println("nearestIndex:"+ret1);
            System.out.println("test:"+ret2);
            System.out.println("Oops!Error!");
            succeed=false;
            break;
        }
    }
    if(succeed==true){
        System.out.println("succeed!");
    }
}

测试结果：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NOHyBbMu-1685076234669)(F:\typora插图\image-20230526110446203.png)]

3、有序数组中找到<=num最右的位置

题意：给定有序数组，在有序数组中找到<=指定数字的最右边的下标，找到返回对应值，找不到返回-1.

解题思路：

  • 数组有序，查找指定元素下标==>二分
  • 在分支条件上动手

优化思路：

  • 在分支条件上动手，同上题，合并两个分支条件，index初值设为-1

核心代码：

public static int nearestIndex(int[] arr,int num){
    int L=0;
    int R=arr.length-1;
    int M=L+((R-L)>>1);
    int index=-1;
    while(L<=R){
        if(arr[M]<=num){
            index=M;
            L=M+1;
        }else{
            R=M-1;
        }
        M=L+((R-L)>>1);
    }
    return index;
}

测试代码：

基本同上，但是注意这次对数器方法需要倒序遍历，找到返回，找不到返回-1

//for test
public static int test(int[] arr,int num){
    for (int i = arr.length-1; i >= 0; i--) {
        if(arr[i]<=num){
            return i;
        }
    }
    return -1;
}
//for test
public static int[] generateRandomArray(int maxSize,int maxValue){
    int[] arr=new int[(int) ((maxSize+1)*Math.random())];
    for (int i = 0; i < arr.length; i++) {
        arr[i]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
    }
    return arr;
}

//for test
public static void printArray(int[] arr){
    for (int cur:arr) {
        System.out.print(cur+" ");
    }
    System.out.println();
}
//    //for test
public static void main(String[] args) {
    int testTime=1000;
    int maxSize=10;
    int maxValue=100;
    boolean succeed=true;
    for (int i = 0; i < testTime; i++) {
        int[] arr=generateRandomArray(maxSize,maxValue);
        int num=(int) ((maxValue+1)*Math.random());

        //使用前提：数组是有序的
        Arrays.sort(arr);

        int ret1=nearestIndex(arr,num);
        int ret2=test(arr,num);
        if(ret1!=ret2){
            printArray(arr);
            System.out.println("num:"+num);
            System.out.println("nearestIndex:"+ret1);
            System.out.println("test:"+ret2);
            System.out.println("Oops!Error!");
            succeed=false;
            break;
        }
    }
    if(succeed==true){
        System.out.println("succeed!");
    }
}

测试结果：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-A9n5RfAR-1685076234670)(F:\typora插图\image-20230526110946676.png)]

4、局部最小值

题意：给定一个数组，已知任一相邻的数都不相等，找到随便一个局部最小值返回。

局部最小值定义：

定义何为局部最小值：
arr[0] < arr[1]，0位置是局部最小；
arr[N-1] < arr[N-2]，N-1位置是局部最小；
arr[i-1] > arr[i] < arr[i+1]，i位置是局部最小；

解题思路：

  • 注意：1.是下标不是值2.边界条件判断：空数组、长度为1的数组、两端判断、中间判断，一共四部分逻辑处理！！！
  • 闭存在与不存在：是不是存在“凹”结构
  • 需要有左右两边淘汰的逻辑，使用二分
  • 遍历范围为可能成为局部最小值的位置：边界位置只需要比较一个位置而中间位置需要比较两个位置，为了统一处理，边界符合条件时单独判断，中间位置使用L、R、M三个指针进行遍历
  • （大体）分支条件的判断从原来的M下标和num比，改成M和M-1及M和M+1比较，两个需要调整的条件都是>，反之就是符合条件的局部最小值
  • （具体到某个分支）每次判断都是为砍范围，缩小范围与另外一边重新构成凹结构，砍到没法再砍了，直接返回对应下标（多结合实例）
    在这里插入图片描述

优化思路：

  • 使用二分法，运用左右淘汰的逻辑
  • 每次三次比较到经典二分三次比较的套用

对数器：

  • 遍历？错

    可能存在多个局部最小值，所以不能通过比对返回的下标，而是拿着下标去验证是不是！！

    当然再次之前需要判断下标是否合法

    这里的对数器可以命名为isRight，返回值为布尔类型

    优化

    • 可以根据index分类讨论：中间有效性、两端有效性
    • 中间index判断可以用三目表达式

核心代码：

注意调整新三分支中的调整条件：

Q1：每次怎么调整？既然没有要求数组有序，那是不是只要mid可以改变就可以，是不是L=M+1和R=M-1的调整条件可以交换？

不是！！

经过开头的预处理，说明该数组上一定存在“凹”结构，那么如果M左边的位置小于它，那么就破坏了整体的这个结构，我们就从右边找,此时右边的结构满足，对应的左边的结构满足，每次把破坏结构的一半砍下去，也一定能够找出来。

Q2：这样一定能找出结果吗？

能的，这是一个算法的结论：即不存在相同元素的数组，一定存在局部最小值

public static int getLessIndex(int[] arr){
    if(arr==null||arr.length==0){
        return -1;
    }
    if(arr.length==1||arr[0]<=arr[1]){
        return 0;
    }
    if(arr[arr.length-1]<=arr[arr.length-2]){
        return arr.length-1;
    }
    int L=1;
    int R=arr.length-2;
    int M=L+((R-L)>>1);
    while(L<=R){
        if(arr[M]>arr[M-1]){//砍左边
            R=M-1;
        }else if(arr[M]>arr[M+1]){//砍左边
            L=M+1;
        }else{
            return M;
        }
        M=L+((R-L)>>1);
    }
    return -1;
}

测试代码：

  • 数组不需要严格有序
  • 数组中不能有重复元素——赋值时做一个do while循环
//for test
public static boolean isRight(int[] arr,int index){
    if(arr.length<=1){
        return true;
    }
    if(index==0){
        return arr.length==1||arr[0]<arr[1];
    }
    if(index==arr.length-1){
        return arr[index]<arr[index-1];
    }
    return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
}
//for test
public static int[] generateRandomArray(int maxSize,int maxValue){
    int[] arr=new int[(int) ((maxSize+1)*Math.random())+1];
    arr[0]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
    for (int i = 1; i < arr.length; i++) {
        do {
            arr[i]= (int) ((maxValue+1)*Math.random())-(int) ((maxValue+1)*Math.random());
        }while(arr[i]==arr[i-1]);
    }
    return arr;
}

//for test
public static void printArray(int[] arr){
    for (int cur:arr) {
        System.out.print(cur+" ");
    }
    System.out.println();
}
//for test
public static void main(String[] args) {
    int testTime=1000;
    int maxSize=10;
    int maxValue=100;
    boolean succeed=true;
    for (int i = 0; i < testTime; i++) {
        int[] arr=generateRandomArray(maxSize,maxValue);

        int index=getLessIndex(arr);
        if(!isRight(arr,index)){
            printArray(arr);
            System.out.println("getLessIndex:"+index);
            System.out.println("Oops!Error!");
            succeed=false;
            break;
        }
    }
    if(succeed==true){
        System.out.println("succeed!");
    }
}

测试结果：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HLlEoZ5m-1685076234670)(F:\typora插图\image-20230526123206885.png)]

二分法总结

算法描述：不断对闭区间（其实有时候处理的是半开半闭区间、开区间）一分为二的方法。

基本思想：一分为二

使用场景：

  • 有序数组查找指定元素/下标
  • 无序数组（满足左右淘汰逻辑）查找指定元素/下标

例题总结：

  • 有序数组查找指定元素：数组必须预处理保证有序，三分支均为arr[M]与num比较，调整放到分支外
  • 有序数组查找>=num最左边的位置：即查找数组中大于等于num的最小值的下标。其中一和arr[M]>num分支合并，不断更新,更新方向R=M-1
  • 有序数组查找<=num最右边的位置：即查找数组中小于等于num的最大值的下标。其中一和arr[M]<num分支合并，不断更新，更新方向L=M+1
  • 局部最小值：空数组、长度为1的数组、两端判断、中间判断，一共四部分逻辑处理，缩小范围的调整结合趋势图分析，实在不行再看运行结果

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/22992.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

IOC初始化 IOC启动阶段 (Spring容器的启动流程)

IOC初始化 IOC启动阶段 (Spring容器的启动流程)

[toc](IOC初始化 IOC启动阶段 (Spring容器的启动流程)) IOC初始化 IOC启动阶段 (Spring容器的启动流程) Resource定位过程&#xff1a;这个过程是指定位BeanDefinition的资源&#xff0c;也就是配置文件&#xff08;如xml&#xff09;的位置&#xff0c;并将其封装成Resource对…
阅读更多...
拥抱新时代的Java

拥抱新时代的Java

原文链接 拥抱新时代的Java Java作为面向对象编程的王牌语言&#xff0c;曾经风靡一时&#xff0c;在Web领域是绝对的老大。随着时间的推移&#xff0c;一些新的编程范式不断的涌现&#xff0c;如函数式编程&#xff0c;响应式编程&#xff0c;以及对函数的全力支持&#xff0…
阅读更多...
node.js+vue房屋租赁管理系统z0g8w

node.js+vue房屋租赁管理系统z0g8w

本系统主要包括以下功能模块&#xff1a;租户、出租人、房源信息、预约看房、合同信息等模块。 其中设计的主要功能如下&#xff1a; &#xff08;1&#xff09;用户的注册和登录本系统&#xff0c;登录到系统的首页。 &#xff08;2&#xff09;用户可以发布自己的房源信息…
阅读更多...
强化学习：值迭代和策略迭代

强化学习：值迭代和策略迭代

值迭代 通过上一章的学习&#xff0c;我们知道了贝尔曼最优方程的求解实际上分两部分&#xff0c;一是给定一个初始值 v k v_k vk​ 找到最优策略 π k 1 π_{k1} πk1​ &#xff0c;二是更新 v k 1 v_{k1} vk1​   下面&#xff0c;我们将详细剖析这个算法&#xff0…
阅读更多...
RabbitMQ

RabbitMQ

处理问题 服务异步调用 两个服务调用时&#xff0c;我们可以通过传统的HTTP方式&#xff0c;让服务A直接去调用服务B的接口&#xff0c;但是这种方式是同步的方式&#xff0c;虽然可以采用SpringBoot提供的Async注解实现异步调用&#xff0c;但是这种方式无法确保请求一定回访…
阅读更多...
从Redisson的RedissonSemaphore引发的信号量实际含义的思考

从Redisson的RedissonSemaphore引发的信号量实际含义的思考

Semaphore到底该如何使用 事情的起因是最近在看redisson的源码&#xff0c;刚好看到了RedissonSemaphore的acquire/release实现。 public RFuture<Void> releaseAsync(int permits) {if (permits < 0) {throw new IllegalArgumentException("Permits amount ca…
阅读更多...
ThingsBoard教程（五十）：规则节点解析 创建关系节点Create Relation Node，删除关系节点 Delete Relation Node

ThingsBoard教程（五十）：规则节点解析 创建关系节点Create Relation Node，删除关系节点 Delete Relation Node

创建关系节点 Create Relation Node Since TB Version 2.2.1 根据类型和方向，从所选实体创建到消息发起方的关系。 以下消息发起方类型被允许：资产、设备、实体视图、客户、租、仪表板。 通过元数据键模式查找目标实体，然后在源实体和目标实体之间创建关系。 如果选择的…
阅读更多...
ASP.NET Core 使用Filter和Redis实现接口防重

ASP.NET Core 使用Filter和Redis实现接口防重

背景 日常开发中&#xff0c;经常需要对一些响应不是很快的关键业务接口增加防重功能&#xff0c;即短时间内收到的多个相同的请求&#xff0c;只处理一个&#xff0c;其余不处理&#xff0c;避免产生脏数据。 这和幂等性&#xff08;idempotency&#xff09;稍微有点区别&am…
阅读更多...
每日一练 | 网络工程师软考真题 Day12

每日一练 | 网络工程师软考真题 Day12

阅读以下说明&#xff0c;答复以下【问题1】至【问题3】 【说明】 某单位有1个总部和6个分部&#xff0c;各个部门都有自己的局域网。该单位申请了6个C类IP地址202.115.10.0/24~202.115.15.0/24&#xff0c;其中总部与分部4共用一个C类地址。现方案将这些部门用路由器互联&…
阅读更多...
Mit6.006-problemSet03

Mit6.006-problemSet03

3-1 哈希练习&#xff08;Hash Practice&#xff09; (a) 按顺序插入整数keys A[47, 61, 36, 52, 56, 33, 92]到尺寸为7的哈希表中&#xff0c;使用哈希函数 h ( k ) ( 10 k 4 ) m o d 7 h(k)(10k4)mod7 h(k)(10k4)mod7。哈希表的每个插槽&#xff0c;存储一个key&#xff…
阅读更多...
字节真的是宇宙尽头吗？

字节真的是宇宙尽头吗？

身边在字节的朋友很多人抱怨很卷&#xff0c;但卷到何种程度?很多人没有直观感受。某乎上一个问题(在字节跳动工作是怎样的?)点赞排名第一的回答生动的解释了字节的卷。 租房的舍友在字节工作。 舍友主卧&#xff0c;我次卧。 合租两个月了&#xff0c;我没见过舍友长什么样。…
阅读更多...
日语文法PPT截图31-45

日语文法PPT截图31-45

31 形式名词 とき　ところ 作为形式名词的话&#xff0c;一般是要写假名不写汉字的 相对时态 如果是一般时/将来时とき&#xff0c;就是先做后面的动作&#xff0c;在做前面的动作。 出教室的时候&#xff0c;关灯。 如果是过去时とき那么&#xff0c;是先做前面的动作&#…
阅读更多...
【dfn序+DP】树

【dfn序+DP】树

把一棵树转化成一个序列有三种方法&#xff1a; dfs序 dfn序&#xff08;时间戳&#xff09; 欧拉序 关于这三者的区别&#xff0c;参考这篇博客&#xff0c;讲的超级好&#xff01; 重谈DFS序、时间戳和欧拉序 - Seaway-Fu - 博客园 (cnblogs.com) 题意&#xff1a; 思路…
阅读更多...
SVN 导出改动差异文件

SVN 导出改动差异文件

文章目录 SVN 导出改动差异文件应用场景/背景介绍具体操作方法 SVN 导出改动差异文件 应用场景/背景介绍 当然下面的两个场景介绍可能用分支管理都会有不错的效果&#xff0c;或者更优&#xff0c;只是记录一下思路&#xff0c;用什么还是看大家个人爱好啦 在开发过程中偶尔会…
阅读更多...
1. Ansible介绍，什么是Ansible?Ansible能用来做什么？

1. Ansible介绍，什么是Ansible?Ansible能用来做什么？

什么是Ansible&#xff1f;Ansible能用来做什么&#xff1f; 如果您是系统工程师或IT管理员,或者只是在IT部门工作的任何人,您可能会在环境中执行大量重复性任务, 无论是每天调整大小和创建新主机或虚拟机&#xff64; 在其上应用配置&#xff64; 修补数百台服务器&#xff6…
阅读更多...
不用再找了，你要的国内好用的ChatGPT网站都在这里

不用再找了，你要的国内好用的ChatGPT网站都在这里

&#x1f4a1; 大家好&#xff0c;我是可夫小子&#xff0c;关注AIGC、读书和自媒体。解锁更多ChatGPT、AI绘画玩法。加&#xff1a;keeepdance&#xff0c;备注&#xff1a;chatgpt&#xff0c;拉你进群。 目录 ChatGPT是什么 OpenAI与ChatGPT的发展历程 AI对话聊天 AI文档…
阅读更多...
jdk13至15——文本块特性

jdk13至15——文本块特性

文本块在jdk13中第一次预览&#xff0c;jdk14第二次预览&#xff0c;jdk15正式版&#xff1b; 终于不用在多行字符串中加一堆\n和一堆\"和一堆了&#xff1b; 之前需要这么麻烦&#xff1a; Testvoid test() {String s "testabcd\n" "aaa\n" "…
阅读更多...
AI：Vue2和Vue3的对比

AI：Vue2和Vue3的对比

1. 什么是Vue.js以及Vue.js在前端开发中的重要性。 Vue.js是一个遵循MVVM&#xff08;Model-View-ViewModel&#xff09;模式的前端JavaScript框架&#xff0c;它采用了双向数据绑定和组件化的思想&#xff0c;使得前端开发变得更加简洁、高效、可维护。Vue.js由中国工程师尤雨…
阅读更多...
JNDI学习笔记

JNDI学习笔记

最近在研究JNDI注入漏洞&#xff0c;就先浅浅的学习以下JNDI相关知识。 JNDI对各种目录服务的实现进行抽象和统一化。 在 Java 应用中除了以常规方式使用名称服务(比如使用 DNS 解析域名)&#xff0c;另一个常见的用法是使用目录服务作为对象存储的系统&#xff0c;即用目录服务…
阅读更多...
领导下发紧急且风险大的任务，如何处理？

领导下发紧急且风险大的任务，如何处理？

在遇到这种无法拒绝&#xff0c;明显很难按时交付的紧急任务时&#xff0c;项目经理处理的关键&#xff1a; 1、降低关键干系人期望值 降低关键干系人的期望值&#xff0c;是项目管理非常重要的一门艺术&#xff0c;也是让干系人满意&#xff0c;便于与关系人沟通的关键。 在项…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站