算法设计-二分

一、有序和单调

​ 二分本质上是一种更加智能的搜索状态空间的方式，他需要状态空间的状态呈现一种“有序的一维数组”的形式，然后再进行搜索。所以一开始的排序是无法避免的。

​ 因为二分的写法问题，所以应当怎样排序也是有一定讲究的，所以排序的时候就可以定义一定的比较方式。

​ 如果更加细致的讨论的话，其实有序只是一个“小条件”，比如说很多枚举、搜索类的题目的状态空间也是有序的，但是我们却没有用二分法，这是因为其核心是，适用于二分法的题目，它的状态和解之间的关系是单调的，如下所示

​ 如左图所示，如果我们对于 mid 有了一个讨论，我们就可以根据需求去选择往左或者往右，右图也是同理，我们知道只要小一点就可以将结果置高，那么最终的结果就会变成“到底小多少”，就是一个很容易解决的问题了。

​ 但是如果状态和结果之间的关系并不单调，那么就无法使用二分法了，如下所示

​ 左图还可以使用“三分法”，但是对于右侧，完全没有办法使用“分法”了，但是不可否认，右图的状态空间也是有序的，没准可以用动态规划求解。

---

二、二分模板

​ 二分一共有两个模板，这是因为二分的本质不是通过二分找到“唯一适合“的点，二分一般呈现一种“最优化”的特点，它要找到是“符合条件”的最大的或者最小的。我们下面的讨论，都默认状态空间是增序排列的。

​ 这就导致当 mid 符合条件的时候，我们需要判定该往哪一边走了，通常情况下，我们希望找到约束条件下的最大值，那么就应当向 mid 右侧去寻找，而当我们希望找到约束条件下的最小值，那么就应当向 mid 的左侧去寻找。

​ 在寻找更小的区间的时候，有两个原则需要遵守，一个是缩小后的区间一定是包括 mid 的，是不可以跳过 mid 的，这是因为 mid 可能是唯一的“最优值”，所以是不能跳过的；另一个是一定要在 mid 的基础上进行移动，比如说 mid + 1, mid - 1 这样的移动，这是因为在整数中，如果 right - left = 1 而不进行移动，也就是 left = mid, right = mid ，这就会导致死循环的出现。综上所述，我们一般在 mid 符合约束条件的时候，利用的是 left = mid, right = mid 来确保对于 mid 的保留，而当 mid 不符合条件的时候，进行 left = mid + 1, right = mid - 1 的操作来避免死循环。

​ 同时，需要注意二分法的边界条件，这个其实有多种写法，我选择了 left < right 作为循环的条件，那么退出的时候就有 left == mid == right，可以选择任何一个索引作为最终结果。

​ 最后，还需要注意当搜索不到的情况，最后会返回什么，这取决于区间缩小时的移动条件，如果是 left = mid + 1，那么就会导致在 right 暂停，相反，则在 left 暂停。

​ 所以模板如下，对于选择“最小值”，其中 check(int) 函数用于检测是否满足条件：

// 求符合约束的最小值
while (left < right)
{// 向下取整int mid = (left + right) >> 1;// mid 是满足条件的，那么向左侧搜索，包括 midif (check(mid)){right = mid;}// mid 不满足条件，向右侧搜索，那么最可能满足条件的是 mid + 1else {left = mid + 1;}
}

​ 对于选择“最大值”

// 求符合约束的最大值
while (left < right)
{// 向上取整int mid = (left + right + 1) >> 1;// 如果 mid 满足条件，那么向右侧搜索，包括 midif (check(mid)){left = mid;}// mid 不满足条件，向左侧搜索，最有可能满足条件的是 mid - 1else{right = mid - 1;}
}

​ 对比如下

条目	模板 1	模板 2
目标	求出满足约束的最小值	求出满足约束的最大值
mid 取整方式	向 left 取整	向 right 取整
搜索为空的返回值	状态空间 right	状态空间 left
跳过方向	向右 left = mid + 1	向左 right = mid - 1

---

三、STL 算法

​ 与上面提出的模板类似的 stl 算法是 lower_bound() ，它可以返回第一个大于等于某个值的迭代器，也就是这个值的下界位置

// 在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val);
// 在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

​ 还有一个类似的函数是 upper_bound() ，它可以返回第一个大于某个值的迭代器，也就是这个值的上界位置

// 查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val);
// 查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

​ 然后还有一个 equal_range() ，返回的是两个迭代器的 pair，指明了范围

// 找到 [first, last) 范围中所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val);
// 找到 [first, last) 范围内所有等于 val 的元素
pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

​ 最后还有一个 bin_search() ，返回一个布尔值来确定在有序状态空间中是否有特定值

//查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val);
//根据 comp 指定的规则，查找 [first, last) 区域内是否包含 val
bool binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp);

​ 示意图如下

​ 对于 lower_bound() ，其实本质是模板 1 的设计模式，找到的是符合条件的最小值，其代码如下

template <class ForwardIterator, class T> // ForwardIterator 前向迭代器
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &val)
{// it 对应 midForwardIterator it;// traits 是萃取机的意思，也就是萃取 iterator 里的信息，并给到算法// count 是搜索区间步长，step 是下一步的步长iterator_traits<ForwardIterator>::difference_type count, step;// count 的初始值就是 first 和 last 的距离（first 对应 left，last 对应 right）count = distance(first, last);// 步长大于 0，与 left < right 相同while (count > 0){it = first;// 二分step = count / 2;// 等价于 mid = left + (right - left) / 2advance(it, step);// 判断 mid 是否满足条件// mid 此时不满足条件if (*it < val) // 或者 if (comp(*it,val))，对应第 2 种语法格式{// first = mid + 1first = ++it;// count 约缩小一半count -= step + 1;}// mid 满足条件，缩小步长（与使用 last 类似）else{count = step;}}return first;
}

​ 因为与模式 1 相似，所以当不存在相似的值的时候，返回的迭代器等于 last 。

​ upper_bound() 的本质依然是模板 1，因为它寻找的是满足大于搜索值的最小值，所以代码结构与 lower_bound() 相同。

template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &val)
{ForwardIterator it;iterator_traits<ForwardIterator>::difference_type count, step;count = std::distance(first, last);while (count > 0){it = first;step = count / 2;std::advance(it, step);// 与 lower_bound() 只有这里不同，此时表示 mid 不满足大于的条件if (!(val < *it)) // 或者 if (!comp(val,*it)), 对应第二种语法格式{first = ++it;count -= step + 1;}else{count = step;}}return first;
}

​ 同样的，当不存在相似的值的时候，返回的迭代器等于 last 。

​ equal_range() 本质就是调用了 lower_bound() 和 upper_bound() ，如下所示

template <class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T &val)
{ForwardIterator it = std::lower_bound(first, last, val);return std::make_pair(it, std::upper_bound(it, last, val));
}

​ binary_search() 调用了 lower_bound() ，将返回值与 last 比较，并且确定搜索值比最小值（first）小（这是搜索不到的情况）

template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T &val)
{first = std::lower_bound(first, last, val);return (first != last && !(val < *first));
}

---

四、二分验证法

​ 这是一类固定的题型，一般呈现“最小最大值”这样的特点（并不绝对），其本质是其答案的状态空间呈现很好的线性有序性（说不定就是个 $[0,max)$ 的区间），我们可以通过二分答案的方法，获得 mid 值，然后利用这个 mid 值去进行模拟验证，如果可以的话，那么就二分继续搜索。

​ 比如说下面的这题

[NOIP2015 提高组] 跳石头

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L\ge 1$ 且 $N\ge M\ge 0$。

接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i(0<D_i<L)$， 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

样例 #1

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 1 说明

将与起点距离为 $2$和 $14$ 的两个岩石移走后,最短的跳跃距离为 $4$(从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石,或者从距离 $21$ 的岩石跳到终点)。

数据规模与约定

对于 $20\%$的数据，$0\le M\le N\le 10$。
对于 $50\%$ 的数据，$0\le M\le N\le 100$。
对于 $100\%$的数据，$0\le M\le N\le 50000,1\le L\le 10^9$。

​ 可以看到这个题目的答案空间是在 $[0,L)$ 之间的，虽然题目看着很复杂，但是如果考虑用二分的方法去做，对于每一个 mid 值的检验，是很容易进行模拟的，如下所示

#include <bits/stdc++.h>using namespace std;int l, m, n;
int d[50005];// 对于传入的 mid，进行模拟检验
bool check(int step)
{int cnt = 0;int pre = 0;for (int i = 0; i <= n; i++){// 如果距离小于 step，说明需要将这个石头移除if (d[i] - pre < step){cnt++;}// 否则就更新前一个木桩else{pre = d[i];}}// 最终的结果是移除的石头不能多余 mreturn cnt <= m;
}int main()
{cin >> l >> n >> m;for (int i = 0; i < n; i++){cin >> d[i];}d[n] = l;int left = 0, right = l + 1;// 因为是求解最大值，所以采用的是模板 2while (left < right){int mid = (left + right + 1) >> 1;if (check(mid)){left = mid;}else{right = mid - 1;}}cout << left;return 0;
}

​ 需要注意的是，在 check() 中，因为采用的是模拟方法，所以可能会导致复杂度比较高，所以当模拟到失败的时候，需要进行减枝优化。比如说洛谷上的这道题目 https://www.luogu.com.cn/problem/P3853 ，它的格式基本上与前面的题目相同，但是在 check() 上进行减枝

bool check(int step)
{int cnt = 0, pre = 0;for (int i = 0; i < n;){if (d[i] - pre > step){cnt++;pre += step;}else{pre = d[i];i++;}// 减枝if (cnt > m){return false;}}return true;
}

---

五、实数二分

​ 实数二分的模板要更加容易记忆，唯一需要注意的就是精度问题，因为控制不好精度，很容易导致死循环（似乎到了 1e-7 左右就容易 tle，这可能是由于双精度浮点数的精度相比较大导致的，所以一般采用 1e-6），一定要注意题目中的描述，模板如下

double left = 0, right = 1e10;
while (left + 1e-6 < right)
{double mid = (left + right) / 2;if (check(mid)){left = mid;}else{right = mid;}
}