The first time I learned about dichotomy was in the math class of high school. I didn’t feel difficult at that time. After all, the idea is very simple. But in the code implementation will encounter a lot of difficulties, the most common is also the most difficult integer binary boundary problem.

Integer binary

The main idea

The idea of integer bisection is as follows: divide the sequence of integers into two ends, the boundary meets the condition, and divide the interval into the left and right parts, the left side meets the condition, the right side does not meet the condition (or vice versa). Now we use dichotomy to find the boundary between the left and right parts. Therefore the so-called binary algorithm, we know that the current candidate interval, there must be, we are going to find the answer, but we found the interval has the nature of the monotonicity such so we can continuously reduce the scope of the candidate interval to eliminate the effect of useless answer is to find the right answer (border).

An integer bisection has two boundaries, the left and right, that is, the boundaries of the left and right halves are not the same point, but two adjacent points, as shown in the sketch below:

This gives us two templates for our dichotomy, one for the red boundary on the left and one for the green boundary on the right. If (mid) = mid (mid)); if(mid) = mid (mid); if(mid) = mid (mid)) = mid (mid); If it’s on the right, r equals mid. And then you fill out the else part, and then finally if you put the else -, you put +1 in the mid declaration; Vice versa. (The simple memory is that the increment of mid is required only when the update l = mid is used.)

The template

bool check(int x){/* Check if x satisfies a condition */};
/ / binary
void bsearch_one(int l,int r){
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;/ / check
        else l = mid + 1; }}void bsearch_two(int l,int r){
    while(l < r){
        int mid = (l + r + 1) > >1;
        if(check(mid)) l = mid;/ / check
        else r = mid - 1; }}Copy the code

example

Given an integer array of ascending length nn, and qq queries.

For each query, return the starting and ending positions of an element kk (positions counting from 00).

If the element does not exist in the array, -1 -1 is returned.

Input format

The first line contains the integers NN and QQ, representing the array length and the number of queries.

The second line contains nn integers (all in the range from 1 to 100001 to 10000), representing the complete array.

The next QQ lines, each containing an integer Kk, represent a query element.

The output format

A total of QQ lines, each line contains two integers, indicating the start and end position of the element.

If the element does not exist in the array, -1 -1 is returned.

Data range

1 n 1000001 n, 100000 or less or less or less or less 1 q 100001 q, 10000 or less or less or less or less 1 k or less 100001 k or less or less 10000 or less

Example Input:

6, 3, 1, 2, 2, 3, 3, 4, 3, 5Copy the code

Example output:

3, 4, 5, 5-1Copy the code
//foreverking
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;

const int N = 100001;

int n,q,x;
int a[N];

int main(){
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> a[i];

    while(q--){
        cin >> x;
        int l = 0,r = n - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if(a[l] ! = x) cout <<"-1 -1" << endl;
        else{
             cout << l << ' ';
             // find the left margin, the second template
             int l = 0,r = n - 1;
             while(l < r){
                 int mid = (l +  r + 1) > >1;
                 if(a[mid] <= x) l = mid;
                 else r = mid - 1; } cout << l << endl; }}return 0;
}
Copy the code

Find the left and right boundaries for the answer. If you can’t find any, print -1.

Floating-point binary

Floating point dichotomy is much easier because there is no boundary problem.

The template

// Float binary
bool check(double x) {/ *... * /} // Check if x satisfies some property

void bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps stands for precision, depending on the accuracy required by the topic
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        elsel = mid; }}Copy the code