不需要考虑mid+1、mid-1的二分查找模板,希望大家都能学会

这篇具有很好参考价值的文章主要介绍了不需要考虑mid+1、mid-1的二分查找模板,希望大家都能学会。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、模板示范

    闫而总之,只要所要寻找的数组能够满足某一条件而被分成两边,就能进行二分,这边我们就拿有序数组的二分来做例子;
    假设目前有这么一组数据:1 2 2 3 3 4 下标从0开始

mid-1 mid+1,c++,算法
    假设此时的情景为,需要我们找到第一个>=3的数字,试想一下,如果能把整个区间分了两半,左边是<3的区间,右边是>=3的区间 如图:

mid-1 mid+1,c++,算法
   那么右区间的第一个点,就是我们找到的符合>=3的第一个数字,将区间分为两半,是不是非常清晰!
   我先给出代码实现(不要害怕 马上就能见证奇迹)

#include<iostream>
using namespace std;
int main()
{
int a[6]={1,2,2,3,3,4};
int l=-1,r=6;//定义两个指针
while(l+1!=r)
{
	int mid=l+r>>1;//(相当于(l+r)/2)
	if(a[mid]<3) l=mid;//或者if(a[mid]>=3) r=mid;
	else r=mid;		   //	 else l=mid;
}
cout<<"第一个3所在的下标为  "<<r<<endl;
return 0;
}	
返回的结果为:第一个3所在的下标为  3

最后二分的结果就是下面这个图,是我们想要的样子!
然后因为我们要找到的是第一个>=3的数字,所以就取 r 也就是>=3区间的第一个数字;
mid-1 mid+1,c++,算法

二、模板

对于一个有序数组,假设下标为0,1,2,3…,n-1;总共n个数字
那么模板为

int L=-1,R=n;
while(L+1!=R)
{
	int mid=L+R>>1;
	if(check()) L=mid;
	else R=mid;
	//最后根据你所分左右两边区间的结果
	//选取L或者R作为结果
}

三、细节说明

为什么L的初始值为-1,R的初始值为N

   首先,如果二分本来就没有结果
比如对于本文例题 1 2 2 3 3 4,,如果你要寻找第一个 >=5 的数,你会发现,整个过程都在执行L=mid,最后得到的结果中,R是等于下标6的,他明显这个时候是越界的,说明我们找不到要寻找的数字,而如果我们一开始将R赋值为n-1,也就是赋值为下标5的时候,他返回的R是5,是没有越界的,被我们当成了答案,但其实这时候我们的二分是没有答案的,就发生了错误
   其次,L最小值为-1,R最小值只能取到1,因为L+1!=R为循环结束条件,R最大值为N,同理则L的最大值为N-2,则(L+R)/2的取值范围是 [0,N)
   mid的值始终位于0到N的左闭右开区间里面,不会发生越界的错误;

为什么循环结束的条件是while(L+1!=R)?

   之前学过二分的小伙伴可能会发现,之前学的二分,他循环结束的条件是while(L<R)
   而这边给出的循环条件是while(L+1!=R) 其实,就是当L和R相邻的时候,循环就结束,而原本的while(L<R)
是当两区间重合以后,循环才结束,所以之前我们需要判断对mid进行加一或者减一的操作,而且因为区间重合的问题,最后返回的L、R还要再进行判断,而这边的这个二分,因为区间反回的是不重合的两区间,只有L=mid和R=mid这两种情况,最后根据需要返回L或者R;

不会陷入死循环

   对于比较奇葩的情况,比如数组大小为1或者2
   比如int a[1],b[2];
   由于我们是while(L+1!=R)结束循环,也就是当L和R相邻的时候结束条件
   对于a[1],他的下标为0 此时L=-1,R=n也就是1
   对于b[2],他的下标为0,1 此时L=-1,R=n也就是2
   所以无论何种情况,初始的L+1始终小于R,历经循环后最终L和R相邻,不会出现一开始L就和R重合等情况导致出现while(L+1!=R)循环不能结束的情况

最后

   我们就能够通过二分得到不重合的两区间,而且只需要L=mid和R=mid,不需要考虑L=mid+1,R=mid-1的情况
   且记得一开始对于一个下标为0,1,2…n-1的数组,指针L要赋值为-1,指针R要赋值为n,那么你就学会了
   最后我给出y总基础算法中的二分例题
数的范围的这题的关于这个二分方法的代码实现文章来源地址https://www.toymoban.com/news/detail-783670.html

数的范围
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,q[N];
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&q[i]);
    while(m--)
    {
        int k;scanf("%d",&k);
        //寻找第一个等于K的坐标 我这边让二分的边界定为 左边为<5 右边>=5 则所求为r
        int l=-1,r=n;
        while(l+1!=r)//当l与r没有相接的时候,求边界
        {
            int mid=l+r>>1;
            //下面找第一个>=5的坐标
            if(q[mid]>=k) r=mid;
            else l=mid;
        }
        //此时得到的r是第一个>=5的坐标
        if(q[r]!=k) printf("-1 -1\n");
        else{
            printf("%d ",r);
                //现在找最后一个<=5的数字 我这边让二分的左边为<=5 右边为>5 则所求为ll
                int ll=-1,rr=n;
                while(ll+1!=rr)
                {
                    
                    int mid=ll+rr>>1;
                    if(q[mid]<=k) ll=mid;
                    else rr=mid;
                }
                if(q[ll]!=k) printf("%d\n",r);
                else printf("%d\n",ll);
            }
        
    }
    
}

四、

    例题one数的范围

    例题two数的三次方根

五、相关学习的视频链接-为啥二分查找容易出错

到了这里,关于不需要考虑mid+1、mid-1的二分查找模板,希望大家都能学会的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 无代码可视化开源爬虫软件EasySpider,希望能帮到大家

    EasySpider是一款可视化爬虫软件,此软件可以让大家使用图形化界面,无代码可视化的设计和执行爬虫任务。只需要在网页上选择自己想要爬的内容并根据提示框操作即可完成爬虫设计和执行。同时软件还可以以Web服务的方式进行API调用,从而可以很方便的嵌入到其他系统中。

    2024年02月10日
    浏览(46)
  • 出现身份验证错误,无法连接到本地安全机构 顺利解决这个问题希望能帮助大家

    出现身份验证错误,无法连接到本地安全机构,远程计算机:XX,这可能是由于密码过期,如果密码已过期请更新密码。 我们可以在系统属性中对远程进行设置,以解决远程桌面无法连接到本地安全机构这一问题。 步骤1.  按 “Windows + R” 键,并输入 “sysdm.cpl” ,点击 “确

    2024年03月22日
    浏览(52)
  • C语言实现万年历(附代码) 小白完成的第一个C语言程序,希望大家多多关注,点赞

    C语言实现万年历 前言:本文章向大家介绍如何使用C语言代码实现万年历使用实例,讲解编写万年历的方法,教你轻松学会写出万年历。这个小程序算是我自己写的第一个比较完整的小程序,算是对大一上学期学习的C语言程序设计基础的一个总结 知识强调 1.由于教皇格里戈

    2024年02月11日
    浏览(36)
  • 云原生是什么?和Docker、K8s是什么关系?又带来了何种影响?希望这篇文章给自己及大家解点疑惑

    现在容器化和云原生十分火爆,但如果要理解为什么这个技术在近几年突然爆火,身为传统的Springboot和Springcloud体系开发者都有很多困惑,怎么就突然这么火爆了呢?诸如我就产生了以下问题: 传统的springboot或springcloud体系和云原生对比起来有何差别? 传统的spring体系和云

    2024年02月07日
    浏览(38)
  • 问题 C: 二分查找右侧边界(C++)(二分查找)

    1.题目描述 2.AC 问题 C: 二分查找右侧边界 时间限制: 1.000 Sec  内存限制: 128 MB 提交 状态 题目描述 请在一个有序不递减的数组中(数组中的值有相等的值),采用二分查找,找到最后1次出现值x的位置,如果不存在x请输出-1。 请注意:本题要求出q个x,每个x在数组中第一

    2024年02月03日
    浏览(44)
  • 二分查找入门教学(动态讲解图、模拟示例、二分查找代码讲解)

    博客昵称: 吴NDIR 个人座右铭:得之淡然,失之坦然 作者简介:喜欢轻音乐、象棋,爱好算法、刷题 其他推荐内容: 计算机导论速记思维导图 其他内容推荐: 五种排序算法 在这个愉快的周末让我们聊一下 二分查找 吧!二分查找是一种很常用的算法,可帮助我们在有序数

    2023年04月18日
    浏览(45)
  • 什么情况需要考虑 mysql 分表

    最近看到公司的其中一个数据库用户表每个月都要几百万的新用户数据增加,目前单表已经是两千多万了。所以找了 DBA 讨论,发现以前学的知识,以及网上的一些资料其实说的并不是很正确,比如 mysql 单表不建议超过一千万,我司 DBA 数据规范建议是单表最多不超过五千万

    2023年04月23日
    浏览(44)
  • 二分查找(整数二分)

    二分法,即二分搜索法,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法。 例如,如果一个序列是有序的,那么可以通过二分的方法快速找到所需要查找的元素,相比线性搜索要快不少。 此外二分法还能高效的解决一些单调性判定的问题。 二分的关键不在于

    2024年02月08日
    浏览(50)
  • 系统上公有云安全需要考虑什么?

    最近在项目合作中涉及到部分业务需要上公有云,但翻了一些公开材料没有发现很好的介绍业务上公有云安全应该怎么做,故整理一篇材料分享业务上公有云应该怎么实践,本人水平有限难免疏漏,当作抛砖引玉了,欢迎同仁交流。 随着信息化的程度加深,一般来说客户上云

    2024年02月02日
    浏览(37)
  • 进一步了解C++函数的各种参数以及重载,了解C++部分的内存模型,C++独特的引用方式,巧妙替换指针,初步了解类与对象。满满的知识,希望大家能多多支持

    C++的编程精华,走过路过千万不要错过啊!废话少说,我们直接进入正题!!!! 函数默认参数 在C++中,函数的形参列表中的形参是可以有默认值的。 语法 : 返回值类型 函数名 (参数 = 默认值){} 示例 : 函数占位参数 C++中函数的形参列表里可以有占位参教,用来做占位

    2023年04月17日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包