Android integer binary template completely solves boundary problem

1. Interval

 //The interval is divided into [l, mid] and [mid+1,r], as follows, the judgment conditions of x<=a[mid], so that x is either in [l, mid], or [mid+1,r]//In the end l will be equal to r     while(l&lt;r)
        {
            int mid=l+r&gt;&gt;1;
            if(a[mid]&gt;=x)r=mid;
            else l=mid+1;
        }
 //The interval is divided into [l, mid-1] and [mid,r], as follows, the judgment conditions of x>=a[mid], so that x is either in [l, mid-1], or [mid,r]        while(l&lt;r)
        {
            int mid=l+r+1&gt;&gt;1;
            if(a[mid]&lt;=x)l=mid;//No 1 dead loop condition            else r=mid-1;
        }
 

• When there are multiple consecutive x in a monotonic interval, the first template will take the leftmost x subscript, because when x==a[mid], the boundary is compressed to the left. Similarly, the second one takes the x subscript on the rightmost
• The second template calculates mid to +1. Because when the interval length is 2, mid is calculated equal to l, while the second template has a dead loop condition: mid assigns a value to l.

2. Example

01: Find the closest element

Total time limit:1000ms Memory limit: 65536kB

describe:

In a non-descending sequence, find the element closest to the given value.

enter:

• The first line contains an integer n, which is the non-descending sequence length. 1 <= n <= 100000.
• The second line contains n integers, which are elements of non-descending sequence. All elements have a size between 0-1,000,000,000.
• The third line contains an integer m, which is the number of given values ​​to be asked for. 1 <= m <= 10000.
  

Next m rows, each row is an integer, to ask for the given value closest to the element. All given values ​​have a size between 0-1,000,000,000.
Output
m rows, each row has an integer, which is the element value closest to the corresponding given value, maintaining the input order. If multiple values ​​satisfy the condition, the smallest one is output.

Sample input:

3
2 5 8
2
10
5

Sample output:

8
5

AC code:

#include <iostream>

using namespace std;

const int N=1e5+5;

int n,a[N],m,x,l,r,i;

bool check(int u)
{
 //The following two judgment conditions are OK //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;
     //Binding means considering when to compress left and when to compress right     while(l<r)
     {
      int mid=l+r>>1;//Because mid is rounding down, mid will never get the initial right boundary      //Similarly, the second template will never get the initial left boundary      if(check(mid))r=mid;//Compress to the left if the conditions are met      else l=mid+1;//Compress to the right     }
     cout<<a[l]<<endl;
    }
    return 0;
}

This is the article about Android integer binary templates that completely solve boundary problems. For more related content on Android to solve boundary problems, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!