栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

二分查找两种情况

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二分查找两种情况

1:查找小于等于x的第一个元素

int min_x(int x){//查找不小于x的第一个元素 
    int l=0,r=n-1;
    while(l>1;
        if(a[mid] 

当a[mid]

当a[mid]>=x时,其右边的元素也一定>=x,我们要找<=x的第一个位置,所以把右边消掉,保留mid;

2:查找大于等于x的第一个元素

int max_x(int x){//查找不大于x的第一个元素 
    int l=0,r=n-1;
    while(l>1;//避免死循环 
        if(a[mid]>x) r=mid-1;
        else l=mid;
	//由于l+r>>1是向下取整,所以上面不加1有可能这一步死循环 
    }
    if(a[l]==x) return l;
    else return -1;
}

当a[mid]>x时,其右边的数一定>x,所以消掉右边;

a[mid]<=x时,其左边的书一定<=x,把mid左边消掉,保留mid;

我们找>=x的第一个元素,由于>>运算符向下取整,mid=l+r>>1,只会取到l,所以如果a[mid]一直 <=l,会陷入死循环;mid应该=l+r+1>>1

 输入样例:

1 2 2 3 3 4

输出样例:

3 4

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/630424.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号