android整數(shù)二分模板怎么解決邊界問題

本篇內(nèi)容主要講解“android整數(shù)二分模板怎么解決邊界問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“android整數(shù)二分模板怎么解決邊界問題”吧!

1.區(qū)間

 //區(qū)間分為[l,mid]和[mid+1,r],如下，x<=a[mid]的判斷條件，使得x要么在[l,mid],要么[mid+1,r]
//最終l會(huì)等于r
     while(l<r)
        {
            int mid=l+r>>1;
            if(a[mid]>=x)r=mid;
            else l=mid+1;
        }
 //區(qū)間分為[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死循環(huán)條件
            else r=mid-1;
        }

• 當(dāng)一個(gè)單調(diào)區(qū)間中有連續(xù)多個(gè)x時(shí)候，第一個(gè)模板會(huì)取到最左邊那個(gè)x下標(biāo)，因?yàn)閤==a[mid]時(shí)候是邊界向左壓縮。同理，第二個(gè)取到最右邊的x下標(biāo)

• 第二個(gè)模板算mid要+1因?yàn)閰^(qū)間長(zhǎng)度為2時(shí)，mid算出來等于l,而第二個(gè)模板存在死循環(huán)條件：mid給l賦值。

2.例題

01:查找最接近的元素

總時(shí)間限制:  1000ms 內(nèi)存限制: 65536kB

描述：

在一個(gè)非降序列中，查找與給定值最接近的元素。

輸入:

• 第一行包含一個(gè)整數(shù)n，為非降序列長(zhǎng)度。1 <= n <= 100000。

• 第二行包含n個(gè)整數(shù)，為非降序列各元素。所有元素的大小均在0-1,000,000,000之間。

• 第三行包含一個(gè)整數(shù)m，為要詢問的給定值個(gè)數(shù)。1 <= m <= 10000。
  

接下來m行，每行一個(gè)整數(shù)，為要詢問最接近元素的給定值。所有給定值的大小均在0-1,000,000,000之間。
輸出
m行，每行一個(gè)整數(shù)，為最接近相應(yīng)給定值的元素值，保持輸入順序。若有多個(gè)值滿足條件，輸出最小的一個(gè)。

樣例輸入:

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;
     //二分就是考慮什么時(shí)候向左壓縮什么時(shí)候向右壓縮 
     while(l<r)
     {
      int mid=l+r>>1;//因?yàn)閙id是下取整，所以mid 永遠(yuǎn)不會(huì)取到初始的右邊界 
      //同理，第二個(gè)模板永遠(yuǎn)不會(huì)取到初始的左邊界
      if(check(mid))r=mid;//滿足條件就向左邊壓縮 
      else l=mid+1;//向右邊壓縮 
     }
     cout<<a[l]<<endl;
    }
    return 0;
}

到此，相信大家對(duì)“android整數(shù)二分模板怎么解決邊界問題”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！