[3. binary integer and floating point number]

1. Integer dichotomy

Dichotomous essence

• It's monotonous , It must be two points
• A dichotomous topic , It doesn't have to be monotonous

Ideas : There are two cases , There are two templates

Consider which template to use ：

• Encounter dichotomy , finish writing sth. mid after , First write check function
• according to check(mid) Think about it ,true and false How to update the interval
• If the update interval is l = mid ,r = mid + 1 , At this time to use mid = (l + r + 1) / 2
• If the update interval is r = mid, l = mid + 1, At this time to use mid = (l + r) / 2
  If in the first case ,l = r - 1, Because division is rounding down , therefore mid = l , At this time, the update interval is still [ l , r] Dead cycle .

subject

Given a length in ascending order is n Array of integers for , as well as q A query .

For each query , Returns an element k Starting and ending positions of （ Location slave 0 Start counting ）.

If the element does not exist in the array , Then return to -1 -1.


Input format
The first line contains integers n and q, Represents the length of the array and the number of queries .

The second line contains n It's an integer （ Both in 1∼10000 Within the scope of ）, Represents a complete array .

Next q That's ok , Each line contains an integer k, Represents a query element .


Output format
common q That's ok , Each line contains two integers , Represents the starting and ending positions of the desired element .

If the element does not exist in the array , Then return to -1 -1.


Data range
1 ≤ n ≤ 100000
1 ≤ q ≤ 10000
1 ≤ k ≤ 10000


sample input ：

6 3
1 2 2 3 3 4
3
4
5

sample output

3 4
5 5
-1 -1

Code

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

int main()
{
     
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
  
    while (m --)
    {
     
        int x;
        scanf("%d", &x);
       
        int l = 0, r = n - 1;
       
        while(l < r)
        {
     
           int mid = (l + r) >> 1;
           if (q[mid] >= x) r = mid;
           else l = mid + 1;
         
        }
        if (q[l] != x) cout << "-1 -1"<< endl;
        else 
       {
     
           cout << l << " ";
           int l = 0, r = n - 1;
           while (l < r)
           {
     
               int mid = (l + r + 1) >> 1;
               if (q[mid] <= x) l = mid;
               else r = mid - 1;
           }
           cout << l << endl;
       }
   }
   return 0;
}

2. Floating point binary

• Floating point binary , It will be strictly reduced by half every time , Don't deal with boundary problems
• And integer bisection , Because there are integers , So the reduction is not necessarily half , Boundary issues need to be addressed

Ideas ：

• Same as integer bisection , Only when r - l <= 1e6( Very small number ), At this point, there is no need for dichotomy

Code

Find the root X Value

#include <iostream>
using namespace std;

int main()
{
     
    double x;
    cin >> x;
    
    double l = 0, r = x;
    while (r- l > 1e-8)
    {
     
        double mid = (l + r) / 2;
        
        if (mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf", l);
    return 0;
}

3. Additional templates

Integer dichotomy

bool check(double x){
     /* */}       // Check x Whether it satisfies certain properties 
// Section [l, r] Divided into [l, mid] and [mid + 1, r] When using ;
int bsearch_1(int l, int r)
{
     
   while (l < r)
   {
     
		int mid = l + r >> 1;
       if(check(mid)) r = mid;  //check() Judge mid Is the property satisfied 
       else l = mid + 1;
	}
   return l;
}



// Section [l, r] Divided into [l, mid - 1] and [mid , r] When using ;
int bsearch_2(int l, int r)
{
     
   while (l < r)
   {
     
		int mid = l + r + 1 >> 1;
       if(check(mid)) l = mid;  //check() Judge mid Is the property satisfied 
       else r = mid - 1;
	}
   return l;
}

Floating point number template

bool check(double x){
     /* */}       // Check x Whether it satisfies certain properties 
double bsearch_3(double l, double r)
{
     
   while (l < r)
   {
     
		double mid = l + r >> 1;
       if(check(mid)) l = mid;  //check() Judge mid Is the property satisfied 
       else r = mid ;
	}
   return l;
}