经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 移动开发 » Android » 查看文章
android整数二分模板彻底解决边界问题
来源:jb51  时间:2021/12/20 15:28:30  对本文有异议

1.区间

  1. //区间分为[l,mid]和[mid+1,r],如下,x<=a[mid]的判断条件,使得x要么在[l,mid],要么[mid+1,r]
  2. //最终l会等于r
  3. while(l<r)
  4. {
  5. int mid=l+r>>1;
  6. if(a[mid]>=x)r=mid;
  7. else l=mid+1;
  8. }
  9. //区间分为[l,mid-1]和[mid,r],如下,x>=a[mid]的判断条件,使得x要么在[l,mid-1],要么[mid,r]
  10. while(l<r)
  11. {
  12. int mid=l+r+1>>1;
  13. if(a[mid]<=x)l=mid;//不加1死循环条件
  14. else r=mid-1;
  15. }


  • 当一个单调区间中有连续多个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代码:

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int N=1e5+5;
  6.  
  7. int n,a[N],m,x,l,r,i;
  8.  
  9. bool check(int u)
  10. {
  11. //下面两种判断条件都可以
  12. //if(a[u]>=x||a[u]<x&& (x-a[u])<=(a[u+1]-x))return true;
  13. //return false;
  14. if(a[u]<x&&(x-a[u])>(a[u+1]-x))return false;
  15. return true;
  16. }
  17.  
  18. int main()
  19. {
  20. cin>>n;
  21. for(i=0;i<n;++i)cin>>a[i];
  22. cin>>m;
  23. while(m--)
  24. {
  25. cin>>x;
  26. l=0,r=n-1;
  27. //二分就是考虑什么时候向左压缩什么时候向右压缩
  28. while(l<r)
  29. {
  30. int mid=l+r>>1;//因为mid是下取整,所以mid 永远不会取到初始的右边界
  31. //同理,第二个模板永远不会取到初始的左边界
  32. if(check(mid))r=mid;//满足条件就向左边压缩
  33. else l=mid+1;//向右边压缩
  34. }
  35. cout<<a[l]<<endl;
  36. }
  37. return 0;
  38. }
  39.  

到此这篇关于android整数二分模板彻底解决边界问题的文章就介绍到这了,更多相关android解决边界问题内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号