android整数二分模板彻底解决边界问题
短信预约 -IT技能 免费直播动态提醒
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;
}
- 当一个单调区间中有连续多个x时候，第一个模板会取到最左边那个x下标，因为x==a[mid]时候是边界向左压缩。同理，第二个取到最右边的x下标
- 第二个模板算mid要+1因为区间长度为2时，mid算出来等于l,而第二个模板存在死循环条件：mid给l赋值。
2.例题
01:查找最接近的元素
总时间限制: 1000ms 内存限制: 65536kB
描述：
在一个非降序列中，查找与给定值最接近的元素。
输入:
- 第一行包含一个整数n，为非降序列长度。1 <= n <= 100000。
- 第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
- 第三行包含一个整数m，为要询问的给定值个数。1 <= m <= 10000。
接下来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整数二分模板彻底解决边界问题的文章就介绍到这了,更多相关android解决边界问题内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
