整数二分 个人见解

整数二分是干什么用的

假设红色区域 和 绿色区域 加起来 是我们的一个数组，其中数组的元素都为整数。

其中红色区域内部的数字 满足一种共同的性质，绿色区域内部的数字满足一种共同的性质，由于是整数二分，所以两个区域不是完全连着的。

只要数组当中能够通过两个性质划分开，那么就可以通过二分。

二分的用途是 让我们可以 快速的找到 两个性质的 边界点。

也就是此时用箭头标记的两个点

思路实现和代码实现

二分之所以快，是因为 它每次 会排除当前区域的 一半。

大致思路如下：

首先取 整个 原序列的 中点 下标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$ 的整数数组，以及 $q$ 个查询。

对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 $n$ 和 $q$，表示数组长度和询问个数。

第二行包含 $n$ 个整数（均在 $1\sim 10000$ 范围内），表示完整数组。

接下来 $q$ 行，每行包含一个整数 $k$，表示一个询问元素。

输出格式

共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

$1\le n\le 100000$
$1\le q\le 10000$
$1\le k\le 10000$

输入样例：

6 3
1 2 2 3 3 4
3
4
5
1
2
3
4
5

输出样例：

3 4
5 5
-1 -1
1
2
3

思路

首先这个题目的每次询问是找 起始位置和 终止位置。

我们可以起始位置和终止位置都用一次二分来查找边界点。

我们以这个输入样例 为例子。

假设我要找 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;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

---

完