文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

android整数二分模板怎么解决边界问题

2023-06-22 04:25

关注

本篇内容主要讲解“android整数二分模板怎么解决边界问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“android整数二分模板怎么解决边界问题”吧!

1.区间

 //区间分为[l,mid]和[mid+1,r],如下,x<=a[mid]的判断条件,使得x要么在[l,mid],要么[mid+1,r]//最终l会等于r     while(l<r)        {            int mid=l+r>>1;            if(a[mid]>=x)r=mid;            else l=mid+1;        } //区间分为[l,mid-1]和[mid,r],如下,x>=a[mid]的判断条件,使得x要么在[l,mid-1],要么[mid,r]        while(l<r)        {            int mid=l+r+1>>1;            if(a[mid]<=x)l=mid;//不加1死循环条件            else r=mid-1;        }

2.例题

01:查找最接近的元素

总时间限制:  1000ms 内存限制: 65536kB

描述:

在一个非降序列中,查找与给定值最接近的元素。

输入:

接下来m行,每行一个整数,为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。
输出
m行,每行一个整数,为最接近相应给定值的元素值,保持输入顺序。若有多个值满足条件,输出最小的一个。

样例输入:

3
2 5 8
2
10
5

样例输出:

8
5

AC代码:

#include <iostream>using namespace std;const int N=1e5+5;int n,a[N],m,x,l,r,i;bool check(int u){ //下面两种判断条件都可以 //if(a[u]>=x||a[u]<x&& (x-a[u])<=(a[u+1]-x))return true; //return false; if(a[u]<x&&(x-a[u])>(a[u+1]-x))return false; return true;}int main(){    cin>>n;    for(i=0;i<n;++i)cin>>a[i];    cin>>m;    while(m--)    {     cin>>x;     l=0,r=n-1;     //二分就是考虑什么时候向左压缩什么时候向右压缩      while(l<r)     {      int mid=l+r>>1;//因为mid是下取整,所以mid 永远不会取到初始的右边界       //同理,第二个模板永远不会取到初始的左边界      if(check(mid))r=mid;//满足条件就向左边压缩       else l=mid+1;//向右边压缩      }     cout<<a[l]<<endl;    }    return 0;}

到此,相信大家对“android整数二分模板怎么解决边界问题”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯