二分
二分法用于解决这样一类问题：一个区间能分成左右两部分，左半部分满足性质 \(A\)，右半部分不满足性质 \(A\)。问题的目标是求解这两部分的分界点。
所以二分法和区间里有没有单调性其实没什么关系，但是很多问题里是从单调性导出了上面的性质，上面的性质才是一个问题能用二分法求解的最本质的性质。
二分法每次取区间的中间元素，通过判断区间中点元素 \(a[mid]\) 是否满足性质 \(A\) 就能断定求解目标是在 \(mid\) 的左边还是右边，从而每次把求解区间长度缩减一半。
特点
在整数二分问题里，需要考虑缩减区间时是否要保留 \(mid\) 这个点，也就是说 \(mid\) 是否可能作为解存在。
对于整数二分而言，“求分界点”也就是求左侧部分（满足性质 \(A\)）的最后一个数，或者求右侧部分（不满足性质 \(A\)）的第一个数。
二分过程结束后，\(l\) 或者 \(r\)（用哪个都行，因为最后它俩是相等的）的位置就是所求的位置。
求左侧部分（满足性质 \(A\)）的最后一个数
由于是求左半部分的最后一个数，所以如果区间中点的数 \(a[mid]\) 是满足性质 \(A\) 的，那么 \(a[mid]\) 这个数就是左侧部分的数，它就有可能是“左侧部分的最后一个数”，因此这时候要把区间缩减成包括 \(mid\) 在内的右半部分，也就是从 \([l, r]\) 变成 \([mid, r]\)，因此执行 \(l = mid\)。
如果区间中点的数 \(a[mid]\) 是不满足性质 \(A\) 的，那么 \(a[mid]\) 这个数就是右侧部分的数，所以下一次要把区间从 \([l, r]\) 变成 \([l, mid - 1]\)，因此执行 \(r = mid - 1\)。
在这类问题下，由于涉及 \(l = mid\) 这个操作，所以“计算区间中点 \(mid\)”的这个操作要使用 \(mid = (l + r + 1) / 2\) 来计算。而不能使用 \(mid = (l + r) / 2\) 来计算，当 \(l\) 的值是 \(r - 1\) 的时候，\(mid = (l + r) / 2\) 计算出来的的值是 \(l\)，如果执行了 \(l = mid\) 的操作，那么区间是没有变化的，会陷入死循环。
这是因为除法会自动做下取整，然而计算 \(mid\) 的方法在这类问题里需要是：
\[mid = \lceil \frac{l + r}{2} \rceil \]所以才要用 \(mid = (l + r + 1) / 2\) 来计算上取整后的值。
求右侧部分（不满足性质 \(A\)）的第一个数
由于求的是右侧部分的第一个数，所以如果区间中点的数 \(a[mid]\) 是满足性质 \(A\) 的，那么 \(a[mid]\) 这个数就是左侧部分的数，所以下一次要把区间 \([l, r]\) 变成 \([mid + 1, r]\)，因此执行 \(l = mid + 1\)。
如果区间中点的数 \(a[mid]\) 是不满足性质 \(A\) 的，那么 \(a[mid]\) 这个数就是右侧部分的数，它就有可能是”右侧部分的第一个数“，因此这时候要把区间缩减成包括 \(mid\) 在内的左半部分，也就是从 \([l, r]\) 变成 \([l, mid]\)，因此执行 \(r = mid\)。
在这类问题下，由于涉及 \(r = mid\) 这个操作，所以“计算区间中点 \(mid\)”的这个操作要用 \(mid = (l + r) / 2\) 来计算。
这是因为除法会自动做下取整，计算 \(mid\) 的方法在这类问题里也正好是：
\[mid = \lfloor \frac{l + r}{2} \rfloor \]所以才要用 \(mid = (l + r) / 2\) 来计算下取整后的值。
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> q[i];
while (m -- ) {
int x;
cin >> 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 << r << endl;
}
}
return 0;
}