Essence of dichotomy: there are boundary points that conform to a certain property, which are used to find the boundary of sub interval that conforms to a certain property in a certain interval, or the boundary that does not conform to this property (integer dichotomy, boundary disjoint)

Data with monotonicity can be dichotomized, and data without monotonicity can also be dichotomized.

Key point: the requirement is included in the side of mid, that is, the direction of "=".

Template 1: find the left boundary

//x is the value to be evaluated, that is, the boundary of a certain property
while(l<r)
{
  int mid=r+l>>1;//mid is included in the left interval
if(check(x)) r=mid;//The lock boundary is contained in the left section
else l=mid+1;   //That is, the locking boundary is in the right section
}

Template 2: find the right boundary

while(l<r)
{
int mid=l+r+1>>1;//mid is included on the right
if(check(x)) l=mid;
else r=mid-1;
}

In the printf function, double is the default to output 6 decimal places, while in cout, it is a valid number (and up to 6 significant numbers)

Title Description
Given an array of integers of length n in ascending order and q queries.

For each query, the start and end positions of an element k are returned (the positions are counted from 0).

"- 1" - 1 "is returned if the element does not exist in the array.

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

The second line contains n integers (all in the range of 1 ~ 10000), representing the complete array.

The next q lines, each containing an integer k, represent a query element.

Output format
There are q rows in total, and each row contains two integers, indicating the starting position and ending position of the element.

"- 1" - 1 "is returned if the element does not exist in the array.

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

Sample
Input:
6 3
1 2 2 3 3 4
3
4
5

Output:
3 4
5 5
-1 -1
Dichotomy
The first binary search paper was published in 1946, but the first bug free binary search method only appeared in 1962, which took 16 years.
——I don't know where to look

Integer dichotomy
yxc split template
The essence of dichotomy is dichotomy, not monotonicity.

When you want to find a boundary value that does not satisfy the property (the right boundary value of the red area)

Find the middle value mid = (l+r+1)/2
if(check(mid)) is equal to true or false
check(m) is to check whether M is in the interval that does not meet the property (check whether it is in the red interval)
Update l or r

When you want to find the boundary value satisfying the property (the left boundary value of the green area)
1. Find the middle value mid = (l+r)/2
2. if(check(mid)) is equal to true or false
check(m) is to check whether M is in the interval satisfying the property (check whether it is in the green interval)
3. Update l or r

To sum up the above two dichotomy methods, the steps are as follows:

First write a check function
Determine how to update the interval in the case of check (true and false).
Under the branch of check(m)==true is:
In the case of l=mid, the update method of the intermediate point is m=(l+r+1)/2
When r=mid, the update method of the intermediate point is m=(l+r)/2
This approach ensures:
1. Last l==r
2. The answer reached by the search is a closed interval, that is, a[l] satisfies the check() condition.

Template
acwing 789

//#define judge
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q, k;
int a[maxn];
int main() {
#ifndef judge
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < q; i++) {
    scanf("%d", &k);
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = l + r >> 1;
      if (a[mid] >= k) {
        r = mid;  //In the second case, find the left end point of the green interval
      } else {
        l = mid + 1;
      }
    }
    if (a[l] != k) {
      printf("-1 -1\n");
    } else {
      printf("%d ", l);
      l = 0, r = n - 1;
      while (l < r) {
        int mid = l + r + 1 >> 1;
        if (a[mid] <= k) {//In the first case, find the right endpoint of the red interval
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      printf("%d\n",l);
    }
  }
  return 0;
}

Some other details
Why do I need + 1?
The reason is that if you do not add 1, the mid will get the number rounded down, so it is possible that after [m,r] is updated, m will always be equal to m (in the case of m+1==r), and it will fall into an endless loop.

It's the dividing point. It's looking for the dividing point! It's approaching the dividing point!