分治法(Divide and Conquer)和二分法(Binary Search)都是十分重要的算法思想。

分治法可以将较大规模的问题，拆分为若干与原问题相似的问题，求解后合并到原问题，从而优化复杂度。

二分法，一般是对于一个具有单调性的函数求某个分界点。

本文将讲解对于分治法/二分法的本质理解，全是干货，欢迎细品。

课程大纲：https://www.eriktse.com/algorithm/1215.html

🎈 作者：Eriktse
 🎈 简介：211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
 🎈欢迎加群一起玩耍~QQ群：600240150

分治法

运用分治法需要满足以下条件：

1.该问题的规模缩小到一定的程度就可以容易的解决。
2.该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3.利用该问题分解出的子问题的解可以合并为该问题的解。
4.该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

引用自：https://zhuanlan.zhihu.com/p/72734354

简单了解以上条件后，我们来讲一下分治法的思维步骤 ：

确定问题模型

通过阅读题意，将题意所求转换为一个数学模型。

比如将题目所求的东西转换为求数组的一段区间的和，或者是求某个函数的临界点，或是求某个函数的极大值、极小值，这个一般比较容易分析。

确定拆分（合并）性质

比如题目要求数组的某个区间[l, r]的和，其实可以转换为[l, mid]的和再加上[mid + 1, r]的和。

我们可以发现[l, mid]和[mid + 1, r]这两个区间是可以从[l, r]拆分出来且相互独立的，并且满足合并的性质：

这是显然的，如果你想看更多关于和式的知识，欢迎阅读《【ACM数论】和式变换技术，也许是最好的讲解之一》。

再或者，在归并排序中，题目要求你将区间[l, r]排序，我们就可以将两个子区间[l, mid]，[mid + 1,r]排序后进行合并。

我们可以发现，我们在划分的时候，尽量都从中间划分，因为这样可以使得复杂度尽可能低，并且划分出来的子问题正好可以填满原问题并且没有重叠、支持合并。

上面的例子合并起来都很简单，但是往往我们做题的时候，会在合并过程中处理一些东西，来得到答案。或是像树形DP一样，将子状态向上转移的时候需要做一些处理。总之分析出正确的合并公式是十分关键的！

确定分治终点的解法

在分治终点，一般是规模极小的问题，比如求一个长度为2的区间的和，或者将一个长度为2的区间排序。这个就很容易写了。

小结

分治法往往会生成一棵树，每一个子问题就是树上的一个节点，我们从根节点出发，自顶向下分解问题，也就是从儿子上面找答案，当某个点问题足够简单了，就直接处理，然后向上更新。

二分法

其实二分法应该是属于分治的一种，但是由于在很多时候，习惯于将其分开，且他们的思维过程有比较大的区别，所以我们单独拎出来讲。

二分法一般用于求解一个具有单调性的函数的分界点。

研究单调性

公式显示不全，请移步：https://www.eriktse.com/algorithm/1231.html

或知乎文章：https://zhuanlan.zhihu.com/p/634626310

在二分之前，需要研究函数的单调性。比如我们要求在正整数定义域内函数满足：

的最小的，其中一般是个定值。

我们容易发现在正整数定义域内是单调递增的。

对于其他函数也是类似的进行单调性分析。

确定枚举区间

在进行二分之前，我们需要确定枚举的区间。

我们用l表示左指针，r表示右指针，mid为(l + r) / 2。

我们的答案一定会在区间[l, r]内，所以我们需要选取合适的区间才能保证找到答案。

上面这个例题，我们可以选取l = 0，r = inf。（inf是无穷大的意思）。

这个无穷大我们可以取到8e18（8乘10的18次方）。因为我们知道：

确定判断函数

二分实际上也是一种枚举，不是在枚举过程中，我们通过数学规律舍弃了很大一部分无效解。

在枚举出一个解后，需要通过判断函数（我们一般命名为check()），来判断解属于那一部分（在这个例子中，就是划分为<m和>=m两部分），然后决定l, r的移动。

确定答案

和题意结合，输出对应的答案，这一步尤其要注意，要理解清楚题目的意思，比如第一个大于等于的，最后一个小于的，最后一个小于等于的等等等等。需要自己多加小心。

例题

ETOJ 1017: 求逆序对个数

链接：http://cdn.oj.eriktse.com/problem.php?id=1017

分治法，每次将子区间排序后，将两个排序区间合并，在合并过程中可以处理出逆序对个数。

对于两个已经排序的数组，新产生的逆序对的个数就是从右边区间取出元素时，左边区间剩余的元素的个数cnt。因为这样表示在原数组中有cnt个元素，满足下标小，值大的特性。

ETOJ 1013: 小e的书架

链接：http://cdn.oj.eriktse.com/problem.php?id=1013

这题的题解可以用二分法做，也可以直接数学方法做，具体看这里（E题）：https://www.eriktse.com/algorithm/1224.html