Binary search (integer binary)

Two points search

Binary search, as the name suggests, is a binary search , The most difficult problem in the bisection algorithm is the boundary problem .int l=0,r=n-1;

Generally, there are two methods to take the boundary ： Rounding down mid=(l+r)/2 And rounding up mid=(l+r+1)/2;

The core code boards of the two boundary methods are as follows ：

//1, Rounding down 
int one(int l,int r)
{
    
    while(l<r)
    {
    
        int mid=(l+r)/2;
        if(chack(mid)==true)r=mid;
        else l=mid+1;
    }
    return l;
}
//2. Rounding up 
int tow(int l,int r)
{
    
    while(l,r)
    {
    
        int mid=(l+r+1)/2;
        if(check(mid)==true)l=mid;
        else r=mid-1;
    }
    return l;
}

When rounded down mid=(l+r)/2 when check(mid) Whether the conditions are met , If Meet the conditions It means that the answer to be searched is in the interval [l,mid] Within the interval , to update r=mid ; If Not meeting the conditions It means that the answer is in the range [mid+1,r] Inside , to update l=mid+1.

When rounded up mid=(l+r+1)/2 when check(mid) Whether the conditions are met , If Meet the conditions It means that the answer to be searched is in the interval [mid,r] Within the interval , to update l=mid; If Not meeting the conditions It means that the answer is in the range [l,mid-1] Inside , to update r=mid-1.

Take a chestnut ： Orderly ascending array a[0]~a[7] Respectively 2 3 4 5 6 7 8 9

We need to look it up x=5 First occurrence , namely a[3]; We need to judge a[i]<=x;

1. When mid=(l+r)/2 when

here a[mid]=5, Meet the conditions , We're going to update r=mid

2. When mid=(l+r+1)/2 when

here a[mid]=6, Not meeting the conditions , We're going to update r=mid-1.

Here is a classic binary search question

Input
Input the first line of test data n,m Indicates the length of the array and the number of queries (1<=n,m<=105)
The next line is n A digital A0 . . . An-1 Satisfy Ai<=Ai+1 (1<=Ai<=109)
Then input m That's ok , Each line is a number Qi Asking (1<=Qi<=109)

Output
For each inquiry , If Qi In an array , Output the position of the first occurrence and the last occurrence of two numbers respectively , If Qi It doesn't appear in the array , The output “-1 -1”

Example
Input
10 3
3 3 3 5 5 5 6 7 7 7
5
6
10
Output
3 5
6 6
-1 -1

The code is as follows

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int a[N];

int main()
{
    
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	while(m--)
    {
    
        int x;
        scanf("%d",&x);

        int l=0,r=n-1;
        while(l<r)
        {
    
            int mid=l+r>>1;//mid=(l+r)/2;
            if(a[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(a[l]!=x)cout<<"-1 -1"<<endl;
        else
        {
    
            cout<<l<<" ";// Output left boundary 
            int l=0,r=n-1;// Next, find the right boundary 
            while(l<r)
            {
    
                int mid=l+r+1>>1;//mid=(l+r+1)/2;
                if(a[mid]<=x)l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
}

The above is the integer binary search content in binary search , I believe you have a deeper understanding of dichotomy , Practice is the only criterion for testing truth , Brush questions to consolidate ！！！

If you have any questions, please don't hesitate to comment orn.