二分解题的奇技淫巧都有哪些，你还不会吗？

先说一下我为什么要写这篇文章。

“二分“ 查找 or ”二分“ 答案的思想大家想必都知道吧（如果不懂，可以看一下我之前写的一篇文章）。

二分求解

可是呢？思想都会，做题的时候，就懵圈了。

这个题竟然考的是二分吗？ 我板子用的对着呢，为什么答案不对呢？我的边界该怎么确定呢？等等。。。

我想大家或多或少都有疑惑吧，那么接下来我谈一谈我对”二分“的理解以及自己的解题技巧。

首先，先引入一个题目【数的范围】。

问题引入

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

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

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

输入格式:

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

第二行包含 n 个整数（均在 1∼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

输出样例：

3 4
5 5
-1 -1

这道题目是二分的一个经典题目，我们使用二分的板子就可以解决。下面是我的代码。

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;
const int N = 1e5 + 10;typedef long long LL;
int n, q;
int num[N];int main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin >> n >> q;for (int i = 0; i < n; i ++) cin >> num[i];while(q --) {int target;cin >> target;int l = 0, r = n - 1;while(l < r) {int mid = (l + r) >> 1;if(num[mid] < target) l = mid + 1;else r = mid;}if (num[l] != target) {cout << -1 << " " << -1 << endl;} else {cout << l << " ";r = n - 1;while(l < r) {int mid = (l + r + 1) >> 1;if(num[mid] > target) r = mid - 1;else l = mid;}cout << l << endl;}}return 0;
}

二分重点

以下是“二分”问题的易错点&难点：

• 搜索范围的左右边界如何确定。
  • left = 0 还是 left = -1;
  • right = num.length - 1 还是 right = num.length.
• 搜索停止的条件。
  • while(left < rigth) 还是 while(left <= right).
• 中间值能否加入到左/右边界中。
  • right = mid 还是 right = mid - 1;
  • left = mid 还是 left = mid + 1;
• 中间值 mid 应该如何计算。
  • mid = left + (right - left) / 2 还是 mid = left + (right - left + 1) / 2.

以下重难点的解释，我全用数的范围这道题给大家讲解。

左右边界的确定

情况一

假设我们要寻找大于target的最小值的索引，但是target比原数组num中的所有数据都要大，那么在[0,num.length - 1]的索引范围内就无法找到满足条件的索引，此时就要扩大右边界，也就是令rigth = num.length，此时目标索引就是num.length。而左边界不用动（这里我解释一下，假如target比原数组中的所有数都要小，这个时候大于target的最小值的目标索引就是索引0)。情况一的搜索区间就是[0, num.length]。

target = 87
num[] = {12, 17, 45, 56, 66, 68, 69, 72}
right = 0, left = num.length

因为target要比num中的所有元素都要大，所以应该扩大右边界，令rigth = num.length。

此时搜索区间为[0, num.length]。

情况二

假设我们要寻找小于target的最大值的索引，但是target比原数组num中的所有元素都要小，那么在[0,num.length - 1]的索引范围内就无法找到满足条件的索引，此时就要扩大左边界，也就是令rigth = -1，此时目标索引就是-1。而右边界不用动（这里我解释一下，假如target比原数组中的所有数都要大，这时候小于target的最大值的目标索引就是索引 num.length - 1）。情况二的搜索区间就是[-1, num.length - 1]。

target = 9
num[] = {12, 17, 45, 56, 66, 68, 69, 72}
right = 0, left = num.length

因为target要比num中的所有元素都要小，所以应该扩大左边界，令left = -1。

此时搜索区间为[-1, num.length - 1]。

情况三

假设我们要寻找等于target的索引（一般target都存在），此时搜索区间就是[0, num.length - 1]。如果题目中出现搜索不到的情况，直接返回题目中要求输出的结果即可。

搜索停止条件

情况一

假设在区间[left, right]之间一定有目标索引，那么我们可以令循环截止条件为while(left < right)。当left == right 的时候，目标索引就是left或者rigth。

情况二

假设在区间[left, right]之间不一定有目标索引，那么我们可以令循环截止条件为while(left <= right)。

中间值的归属

对于中间值的归属问题，我这里举具体的例子给大家讲解。

情况一

假设我们要搜索的是 大于9 的最小值索引，如果 num[mid] <= 9，那么这个 mid 一定不是目标索引，此时应该更新左边界 left = mid + 1；如果 num[mid] > 9，那么此时的 mid 有可能是目标索引，此时应该更新右边界rigth = mid。

情况二

假设我们要搜索的是 小于9 的最大值索引，如果 num[mid] >= 9，那么这个 mid 一定不是目标索引，此时应该更新右边界 rigth = mid - 1；如果 num[mid] < 9，那么此时的 mid 有可能是目标索引，此时应该更新左边界left = mid。

情况三

假设我们要搜索的是 等于9 的索引，如果 num[mid] > 9，那么这个 mid 一定不是目标索引，此时更新右边界 right = mid - 1；如果 num[mid] < 9，那么这个 mid 也一定不是目标索引，此时更新左边界 right = mid + 1；如果 num[mid] = 9，那么我们就找到正确答案了。

中间值计算

大家可以看到，之前给大家两种计算中间值的公式分别为：

• 公式一：mid = left + (right - left) / 2，取的是靠近左边的中位数。
• 公式二：mid = left + (right - left + 1) / 2，取的是靠近右边的中位数。
  这里，我先给大家一个比较好记的技巧如果过程中有令mid = left，就用公式二；否则，就用公式一。

接下来说一下为什么要 +1 呢？

假设出现了一种情况left + 1 = right并且mid = left的情况，之后在求 mid的时候，我们使用公式一更新mid，此时mid始终为左边界left，程序就会陷入死循环。所以为了避免这种情况的发生，当出现mid = left的时候，必须使用公式二。

而对于，right = mid这个条件则不用担心，对于C++就是向下取整。

总结

对于以上的二分重点介绍，如果按照以上步骤去考虑问题的话，基本上不会出错。

这里，我给出大家，我自己的解题步骤：

1. 首先审题，判断题目要二分的元素（一般是题目直接要求的答案 or 题目有个固定量，根据固定量而定）；
2. 思考边界该怎么选，是否需要更新左右边界的取值；
3. 判断在题目的范围内是否一定有答案值，确定循环终止的条件（同时确定check函数的编写）；
4. 暂时使用公式一，如果有mid = left，则更换为公式二。