整数二分是干什么用的
假设红色区域 和 绿色区域 加起来 是我们的一个数组，其中数组的元素都为整数。
其中红色区域内部的数字 满足一种共同的性质，绿色区域内部的数字满足一种共同的性质，由于是整数二分，所以两个区域不是完全连着的。
只要数组当中能够通过两个性质划分开，那么就可以通过二分。
二分的用途是 让我们可以 快速的找到 两个性质的 边界点。
也就是此时用箭头标记的两个点
思路实现和代码实现
二分之所以快，是因为 它每次 会排除当前区域的 一半。
大致思路如下：
首先取 整个 原序列的 中点 下标mid（假设该数组下标区间为 [ l, r ] ），然后判断 mid这个数字 满足 这两个性质当中的那一个，通过判断的结果，更改我们的 l 和 r ，同时更新 mid，直到 l 和 r 相遇。
我们来模拟一下。
我们先来找我们的 左边界点。
有一个很关键的点，那就是 找哪边的边界点，就判断哪边的性质，其实判断另一边也行，但是新手的话，建议你这样弄。
由于我们是找 左边界点，所以我们就 判断 mid 是不是满足 我们 红色区域数字的性质。
注意：这里的红色区域和绿色区域的实际大小并不一定是图中画 的看起来的 大小关系。
1.假设我们 的 mid 满足了红色区域，那么就证明 mid 在下列红色区域中。
由于这里并不知道 红色区域 有多长，所以mid 可能是 任意一个红色区域内的地方。
我们的任务是要找 左边界点，那么 发现 mid 左边的 值（不包含 mid）就不可能 是我们的 答案。
所以我们 要更新我们 的 左区间，此时 就需要 l = mid，因为此时 mid有可能是答案。
2.假设我们的mid 不满足红色区域内的性质，那么 说明 mid 此时在 绿色区域内，并且可能是任意地方。
此时会发现，我们找的左边界点 始终在 mid 的左边（结果不可能是mid）.
那么此时就需要更新 我们 的右区间点，也就是 r = mid - 1; 这里减1的原因就是 由于是找 左边界点，所以 mid 不可能是我们的结果。
接着只需要重复此效果，直到 l >= r 时停止。
接着我们把刚才的找左边界点 的思路 转换到代码上。
其中 check 函数为 判断是否 满足 红色区域内的性质，满足则返回 true，否则返回false。
这里值得注意的是，计算 mid 的 方式 不是 l + r >> 1 而是 加了个 1，这个是因为 如果不加1，那么就会导致 死循环。
我们来看下面这个例子。
假设我们的此时 l 和 r 已经紧挨着了，那么正常如果 mid 向下取整的话，那么 mid 就会等于 left。
然而此时如果 满足性质的话，执行的 语句是 l = mid。
那么就会造成 left 永远是left ，left 和 right 将永远无法 等于，所以就陷入了死循环。
所以只要记住，一旦 满足条件后的条件是 l = mid，那么mid 就一定要向上取整。
接下来我们来看找 右边界点的 思路和代码。
其实跟找左边界点时一样。
找哪边，就记得判断哪边，现在我们在找右边的边界点，所以一会判断的是 满不满足右边的性质。
1.如果满足右边的性质，说明此时 mid 在绿色区域范围内。
那么mid 右边 的值 就会排除掉（不包含 mid）,所以此时就需要更新 区间的右端点，由于mid 可能是结果，所以更新语句 为 r = mid；
2.如果此时不满足 绿色区域内的性质，则 mid 在红色区域内，此时 更新语句就为 l = mid + 1.
这里+1的原因 是因为 mid 不可能 是我们的答案。
代码如下：
实战演练
题目
给定一个按照升序排列的长度为 n n n 的整数数组，以及 q q q 个查询。
对于每个查询，返回一个元素 k k k 的起始位置和终止位置（位置从 0 0 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n n n 和 q q q，表示数组长度和询问个数。
第二行包含 n n n 个整数（均在 1 ∼ 10000 1 \sim 10000 1∼10000 范围内），表示完整数组。
接下来 q q q 行，每行包含一个整数 k k k，表示一个询问元素。
输出格式
共 q q q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1 ≤ n ≤ 100000 1 \le n \le 100000 1≤n≤100000
1 ≤ q ≤ 10000 1 \le q \le 10000 1≤q≤10000
1 ≤ k ≤ 10000 1 \le k \le 10000 1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
思路
首先这个题目的每次询问是找 起始位置和 终止位置。
我们可以起始位置和终止位置都用一次二分来查找边界点。
我们以这个输入样例 为例子。
假设我要找 3 的 起始位置和 终止位置。
对于起始位置来说，我们可以把这个区间 按照此图的分法分为两个区域，然后找右边界点。
其中红色区域内数字的值都是 小于 3 的，绿色区域内的值都是 大于等于3的。
这时候我们只需要根据我们刚才讲的 写就行了。
对于终止位置来说，我们可以分为 图片当中的两个区域，然后找左边界点。
其中 红色区域内的值都是 小于等于3的，绿色区域内都是 大于3的。
代码
有了思路，代码就很轻松了。
准备阶段：
输入环节：
询问环节：
接下来就是刚才的思路了，我们先找 起始位置。
这里把3换成 x 就可以了。
相当于这里分成了 < x 和 >= x 两个区域，然后找右边界点。
首先先定义我们区间的 两个端点。
然后再根据我们刚才的思路，就可以成功找到起始位置。
当然前提 你数组里面得有这个值。
所以我们不能直接打印这个起始位置，因为不确定有没有，所以得判断一下。
在结束这个循环后，此时 l 和 r 是相等的，我们可以判断这个值是不是 x ，从而判断数组当中有没有 x。
如果不等于 x 说明此时 x 在数组中不存在，所以就直接输出 -1 -1 然后 continue 继续循环。
在找完了起始位置，接着来找终止位置。
在找终止位置前，我们先把起始位置先打印了。
因为一会我们要 二次利用到这个 l 变量，当然也可以重新创建一个变量，看个人喜好。
这里我们需要 将 r 重新定位到 原数组的右端点。
原本l 和 r 在我们找起始位置后，在能找到值的前提下，都会指向 x 。
此时我们需要将范围 扩大到 能够 容纳下终止位置的范围，所以可以将 r 移动到最右端。
接着我们 再利用之前找左边界 的思路。
注意由于 这里是 l = mid; 所以算 mid 的时候是向上取整。
最后打印l 即可，由于题目格式要求，需要记得换行。
完整代码如下：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, q;
int a[N];
int main()
{
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
while (q--)
{
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)
{
printf("-1 -1\n");
continue;
}
printf("%d ", l);
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;
}
完
