这是一篇面向二分初学者的可视化教程，希望能帮助你们更好的理解二分
因为二分在单调区域的答案查找、枚举算法的优化、等领域有着重要的作用
熟练的掌握二分会在一些题型下极大的降低我们代码的时间复杂度并提高代码执行效率（因为二分的时间复杂度是O(log 2 _2 2?n))
（本博客所有的代码均为c++）
二分的工作原理
相比顺序查找或枚举算法，二分通过对单调的待查找序列或者答案进行一些优化，使得程序的执行效率得到提升。
题型大概分为二分查找与二分答案两种。（其实是因为本蒟蒻就做到过这两种）
二分查找的具体优化为：先确定起始位置i与终点位置j，然后计算中点位置m
通过对中点位置的值与被查找值的大小比较结果，根据中点位置对下一次的起始位置与终点位置进行调整，从而达到降低查找次数的目的
二分答案的具体优化为：题目一般都会有限制条件m（如切割次数，移动次数）一般会有最终需要完成的目标n，一般需要我们求的是n的极值。而相比朴素的依次枚举n，二分答案能通过其机制计算出下一个更合理的n，达到降低复杂度的效果（有一些抽象，之后会有例题解释来帮助理解，其实际操作与二分查找类似）
为了方便大家理解，这里将采用二叉树图像的方式进行可视化讲解。
1、整数域上的二分
二分查找：
查找一个确定存在且唯一的数字
例：有如下数列{1，2，3，4，5，6，7，8，9，10，11，12}
? 下标分别为{1，2，3，4，5，6，7，8，9，10，11，12}
输入一个0~12的整数，要求返回其下标
比如我们要查找的数是key=5
现在我们来分析一下这个查找的过程
| 次数 | i | j | m | 查找到的数字 |
|---|---|---|---|---|
| 1 | 1 | 12 | 6 | 6 |
| 2 | 1 | 5 | 3 | 3 |
| 3 | 4 | 5 | 4 | 4 |
| 4 | 5 | 5 | 5 | 5 |
第一次查找：i=1,j=12,m=6 可知m>key 。因为我们给出的数列是严格单调递增的，那么可以知道：m的右侧，是不可能再有比m小的数了，所以肯定找不到5这个数，当然m本身也不是5，所以我们可以缩小查找的范围[1,12]—>[1,5]，与之对应的操作就是 j=m-1；反之，如果m<key，那么意味着m的左侧不可能找到答案，与之对应的操作就是i=m+1
那么接下来几次查找同理，且如表格所示。
先上二叉树图：（这里我们称每根线为枝，每个椭圆为节点，对于那些不连接节点的枝，我们称它为空枝）
其中椭圆内的数字为下标，代表了查找到的位置（这里也等于下标对应的值）
不难发现，所有数字都在二叉树上以节点的方式出现，且不重复，所以这个二叉树表示了所有可能的查找过程
而节点下方一左一右两根枝条，即对应了二分区域向左移动（即i=m+1）和二分区域向右移动（即j=m-1）两种操作
这里我们不难发现，我们每次进行查找都是从一个节点沿着枝前往下一个节点
接下来上代码
为了表示方便，我们假设数列存储在a[1]—a[12]中
int i = 1, j = 12, key = 5, a[13];
while (i <= j)
{
int m = (i + j) / 2;
if (a[m] > key)
j = m - 1;
else if (m < key)
i = m + 1;
else if (m == key)
{
cout << m << endl;
break;
}
}
这里要注意的是循环条件while(i<=j)
由于上一题中我们将问题简化为
查找一个确定存在且唯一的数字
但是实际情况中不一定能找到，那么再观察我们的二叉树图像，发现有些节点出现了空枝，因此不难推测，从空枝处结束循环就意味这找不到待查找的key。
举个例子，还是上面的数列，如果我们需要查找13这个元素，那么查找时就会沿着最右边的枝一直往右下方下降，最后从12的右枝退出循环
变式：查找一个确定存在但不唯一的数字
例：有如下数列{1，4，6，16，16，16，16，18，21，33}
? 下标分别为{1，2，3， 4， 5， 6， 7， 8， 9， 10}
假设我们要查找的数字key=16
看到这里想必你已经心生疑惑，代码最终查找的结果到底是下标为4的16还是下标为7的16
其实这个取决于你的需要，可以通过改变代码来实现。
这里我们假设需要的是下标为4的16
为了便于理解，先上代码，可以与上一段代码比较下，找找有哪些不同
为了表示方便，我们假设数列存储在a[1]—a[10]中
int i = 1, j = 10, key = 16, a[11];
while (i <= j)
{
int m = (i + j) / 2;
if (a[m] >= key)
j = m - 1;
else
i = m + 1;
}
cout << i << endl;
不难发现，这段代码大致与上一段相似，但是去掉了查找成功就输出并退出循环的判定，而是将查找成功的情况移到了j=m-1对应的情况里，也就是说，哪怕中点m的值等于了key，也不停止查找，而是将下一次查找区域左移，需要格外注意的是，因为缺少了查找成功就退出的判断，所以循环一定会从二叉树的某一个空枝退出，知道了这个，那么接下来的表格和图解也不难理解了
| 次数 | i | j | m | 查找到的数字 |
|---|---|---|---|---|
| 1 | 1 | 10 | 5 | 16 |
| 2 | 1 | 4 | 2 | 4 |
| 3 | 3 | 4 | 3 | 6 |
| 4 | 4 | 4 | 4 | 16 |
| 5 | 4 | 3 | 退出循环 | 退出循环 |
接下来上二叉树图
注意：最终找到的位置应该由i表示，所以最后输出时应该cout<<i<<endl 并且一定有a[j]<key<=a[i](假设a[i]，a[j]都不越界)
那如果我们要找下标为7的16呢？
其实只要删掉if(m>=key)中的等号即可，这样当a[m]==key时，执行的将会是else中的语句，即将下一次查找区域右移
二叉树与上图一样，只不过找下标为4的16时走4这个节点，而找下标为7的16时走18这个节点
值得注意的是，最后的结果由j表示
也就是说最后输出下标时应该cout<<j<<endl;并且一定有a[j]<=key<a[i](假设a[i]，a[j]都不越界)
其实这些熟练后都可以直接作为规律记住，不必再画二叉树
再更进一步，还是a[1]—a[10]这个数列，如果我们要找key=17（即在数列中不存在），i与j各是多少？
答案：i=8,j=7，想想这又意味这什么，又有什么实际的作用
二分答案
我一般把二分答案理解成一种特殊的枚举，但它更加高级，因为他能极大的降低枚举的次数，从代码的实现与执行上说，就是它能降低程序的时间复杂度
先上一个枚举题
现有n根木棍，第i根木棍的长度为a[i]，你有一台切割机，最多可以切割m次，每次切割可以选择一根木棍，将它分成两根整数长度的木棍，问所有切割方法中，所有木棍长度最大值的最小值是多少。
第一行一个数T表示共有T(1<=T<=10)组数据，每组数据满足
第一行两个整数n,m，表示木棍数目和最大切割次数(1<=n,m<=100000)
第二行包含n个整数，第i个数a[i]表示第i根木棍的长度(1<=a[i]<=200)共T行，每行一个数，表示如题所述的答案
样例输入：
1
2 2
1 3样例输出
1
这是一道枚举的模板题，数据很小，a[i] ∈ \in ∈[1,200]
所以直接对木棍的最大值枚举即可
这是AC的代码
#include<bits/stdc++.h>
using namespace std;
int a[100009];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
int max = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] > max) max = a[i]; //确定枚举上界
}
for (int i = 1; i <= max; i++)
{
int sum = 0;
for (int j = 1; j <= n; j++)
{
sum += (a[j] - 1) / i; //如果a[j]能整除i，则可以少切一刀
}
if (sum <= m)
{
printf("%d\n", i);
break;
}
}
}
return 0;
}
那假如数据再大一点呢？
现有n根木棍，第i根木棍的长度为a[i]，你有一台切割机，最多可以切割m次，每次切割可以选择一根木棍，将它分成两根整数长度的木棍，问所有切割方法中，所有木棍长度最大值的最小值是多少。
第一行一个数T表示共有T(1<=T<=10)组数据，每组数据满足
第一行两个整数n,m，表示木棍数目和最大切割次数(1<=n,m<=100000)
第二行包含n个整数，第i个数a[i]表示第i根木棍的长度(1<=a[i]<=100000)共T行，每行一个数，表示如题所述的答案
样例输入：
1
2 2
1 3样例输出
1
注意：这里的a[i] ∈ \in ∈[1,100000] 所以如果还是按上一题的思路来枚举木棍最大值的话肯定是T的
所以这里就要用到二分答案了
先上AC代码
#include<bits/stdc++.h>
using namespace std;
int a[100009];
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, m;
scanf("%d%d", &n, &m);
int max = 0;
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] > max) max = a[i]; //确定二分上界
}
int be = 1, i;
int end = max;
while (be <= end)
{
i = (be + end) / 2;
int sum = 0;
for (int j = 1; j <= n; j++)
{
sum += (a[j] - 1) / i; //如果a[j]能整除i，则可以少切一刀
}
if (sum <= m)
{
end = i - 1;
}
else
{
be = i + 1;
}
}
printf("%d\n", be);
}
return 0;
}
可以看到，上一题中我用i这个变量进行对木棍最大值的依次枚举，而这题我则是以二分答案的形式对i进行赋值
这里我们要找的是使得切割次数少于m次的木棍最大值，这样的答案可能有很多，根据题目的意思，我们应该要找使得切割次数少于m次的木棍最大值的最小值，借鉴上面二分查找的变式，找到符合要求的答案时，把下一次二分的区间向左移动，最后退出循环时就能找到符合题意的木棍最大值的最小值了。
2、实数域上的二分
实数域上的二分一般用for循环解决
下面给出一道例题
给一个方程f(x) = a^x + b^x - c^x = 0, 对于给定的[e, f](e <= f)范围内的数，求解x。
其中a, b, c, e, f均为整数，a, b, c >= 1。有多组测试数据。
对于每组测试数据，有一行，每行5个整数，分别表示a, b, c, e, f。输入数据保证a, b, c, e, f都在32位有符号数表示的范围内，a^x, b^x, c^x在double表示的范围内。
所给数据保证f(x)单调。
如果在指定范围内有解，输出一行，包括x, x精确到小数点后6位。
如果无解，则输出一行"No Answer!"。样例输入
2 3 4 1 2
样例输出
1.507127
给出AC代码
#include<bits/stdc++.h>
#define xe 0.000001
using namespace std;
double e, f, a, b, c;
double hs(double x) //将原题函数封装成自定义函数
{
return pow(a, x) + pow(b, x) - pow(c, x);
}
int main()
{
while (~scanf("%lf%lf%lf%lf%lf", &a, &b, &c, &e, &f))
{
int sign = 1;
double l = e, r = f;
if (hs(l) > hs(r)) sign = -1; //判断递增还是递减
for (int i = 1; i <= 100; i++)
{
double m = (l + r) / 2;
if (sign * hs(m) > 0) r = m; //二分100次求答案
else l = m;
}
if(abs(hs(l))<0.000000001) printf("%.6f\n",l);
else printf("No Answer!\n");
}
}
观察代码可以看到，我采用了for循环二分一百次求答案的方法
这样得到的答案精度足够高，只要在最后判断的时候if(abs(hs(l))<0.000000001)以精度形式判断一下就行，切记不能带入原函数直接判断是否等于0，因为答案本身就可能是一个无限小数，我们有可能求不出答案的精确值。
ps：
本博客仅以本蒟蒻所学整理而来，有任何错误请指出，希望能帮到读者。