android整数二分模板彻底解决边界问题

目录
  • 1.区间
  • 2.例题
    • 01:查找最接近的元素

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解决边界问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • android整数二分模板彻底解决边界问题

    目录 1.区间 2.例题 01:查找最接近的元素 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

  • Android webveiw 出现栈错误解决办法

    Android webveiw 出现栈错误解决办法 前言: 最近做一个项目,项目调试基础库的一个调试工具展示设备信息页面使用WebView.有一个应用集成调试基础库展示内容时出现 java.lang.UnsupportedOperationException: For security reasons, WebView is not allowed in privileged processes 因为应用是系统级别的,在AndroidManifest.xml中添加了android:sharedU

  • PHP之浮点数计算比较以及取整数不准确的解决办法

    php有意思的现象,应该是很多编程语言都会有这样的现象.这个是因为计算机的本身对浮点数识别的问题.....下面通过代码给大家展示下: $f = 0.58; var_dump(intval($f * 100 *100)); //结果5799 var_dump((float)($f * 100 *100)); //结果5800 echo (int)((0.1+0.7)*10); //结果7 echo (float)((0.1+0.7)*10); //结果8 <?php $a = 0.1; $b =

  • Android中使用Theme来解决启动app时出现的空白屏问题

    相信大多数人一开始都会对启动app的时候出现先白瓶或者黑屏然后才进入第一个界面,例如:SplashActivity.那这是什么原因造成的呢? <style name="Splash_Theme" parent="@android:style/Theme.NoTitleBar"> </style> 原因是我们给改Activity/Application设置的主题引起的,因为该主题相对应的windowBackground等背景被设置成了白色或者黑

  • Android webview 内存泄露的解决方法

    Android webview 内存泄露的解决方法 最近在activity嵌套webview显示大量图文发现APP内存一直在涨,没法释放内存,查了很多资料,大概是webview的一个BUG,引用了activity导致内存泄漏,所以就尝试传递getApplicationContext. 1.避免在xml直接写webview控件,这样会引用activity,所以在xml写一个LinearLayout,然后 linearLayout.addView(new MyWebview(getApplicati

  • Android 自定义view模板并实现点击事件的回调

    Android 自定义view模板并实现点击事件的回调

    Android 自定义view模板并实现点击事件的回调 主要的目的就是仿老版QQ的一个界面做一个模板.然后实现点击事件的回调.先看效果图: 步骤如下: 1.在res/values/目录下新建一个atts.xml文件 内容如下: <resources> <declare-styleable name="topbar"> <attr name="title" format="string"/> <attr n

  • Android Handler leak分析及解决办法详解

    Android Handler leak 分析及解决办法 In Android, Handler classes should be static or leaks might occur, Messages enqueued on the application thread's MessageQueue also retain their target Handler. If the Handler is an inner class, its outer class will be ret

  • Android键盘自动弹出解决方法分析

    本文实例分析了Android键盘自动弹出解决方法.分享给大家供大家参考,具体如下: 1.在: 复制代码 代码如下: activity android:name=".Uninstaller" android:label="@string/app_name" android:windowSoftInputMode="adjustPan" 加入了: 复制代码 代码如下: android:windowSoftInputMode="adjustP

  • Android listview的滑动冲突解决方法

    Android listview的滑动冲突解决方法 在Android开发的过程中,有时候会遇到子控件和父控件都要滑动的情况,尤其是当子控件为listview的时候.就比如在一个ScrollView里有一个listview,这种情况较常见,就会出现这种滑动冲突的情况.这种情况也比较常见,有时候就是这样,没法,但是,了解事件分发的我们知道应该怎么处理这样的事情 有两点需要注意: 一般来说,view的onTouchEvent返回true,即消耗点击事件,viewgroup的onInterceptTou

  • Android Studio注释模板介绍

    Android Studio注释模板介绍

    大家啊从Eclipse转到Android Studio很不习惯吧,感觉还是用Eclipse的方法注释模板比较方便,敲/**加回车,模板就加载出来了,而Android Studio却不能自定义,现在用live templates替代,具体方法通过图片和文字的方式展示如下: 步骤 1.File->Setting->Editor->Live Templates 2.点击+,创建一个Template Group 3.填个你要的group名,我的叫custom 4.选中你刚刚创建的group,创建

随机推荐