$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：

整数二分

听说只有$10$%的程序员能写对二分？
这似乎是真的。。。
因为二分看起来简单，实际上有很多细节问题。

二分的本质

给定一个区间，在它上面定义某种性质，使得这种性质在右半部分满足，在左半部分不满足。二分可以用来寻找这个性质的边界。
二分的本质不是单调性，但是有单调性一定可以用二分，没有单调性有可能可以用二分。
有点绕。

求左半部分分界点：
$mid=(l+r+1)/2$
这部分为什么要$+1$呢？
先假设不$+1$：
设$l=r-1$，那么就会死循环，因为$mid=l$，然后更新$l=mid=l$。

1. $if(check(mid))$

   • $mid$在左部分，$ans:[mid,r]$，$l=mid$。

2. $else$

   • $mid$在右部分，$ans:[l,mid-1]$，$r=mid-1$。

求右半部分分界点：
$mid=(l+r)/2$

1. $if(check(mid))$

   • $mid$在右部分，$ans:[l,mid]$，$r=mid$。

2. $else$

   • $mid$在左部分，$ans:[mid+1,r]$，$l=mid+1$。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, 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;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (a[l] != x) cout << "-1 -1" << endl;
        else {
            printf("%d ", l);
            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;
            }  
            printf("%d\n", l);
        }
    }
    return 0;
}