某些数学公式计算的算法中，往往可以使用二分来加速计算速度，这里列举几道常见的算法题。
x的n次方
如计算2^31，则传统做法需要进行30次乘法，效率不高，严重依赖n的大小，怎么优化？
简单的想法是，由于x是固定的，能不能只计算n次的其中一部分，然后推导出整体的结果？
比如二分思想，只计算一半，另一半跟这一半的结果是一样的，直接相乘就可以了
OK，那么这一半的数字怎么快速计算呢？方法是一样的，能不能也计算一半的一半，另一小半就不用计算了…
很明显，这是一个递归的思路！
递归
递归是最容易想到的写法，它的好处就是代码清晰明了。
分治法
divide and conquer，将大问题每次均分为「等价」的两个小问题，通过对小问题的计算的结果的合并得到最终的结果。
「等价」并不是完全相同，因为有时候不能完全平均，需要单独处理奇数的个数的问题。这道题的一个好处是divide后只需要计算一次，
因为两部分的结果是一样的，不像归并排序那样，左右两边都需要单独计算。
递归思路：
- 首先找到「出口」，由于每次都计算当前数据量的「一半」并求值，那么自然想到最小的量就是
0了，此时直接返回1（因为是乘法计算） - 找到参数变化的可能性：每次计算都是将当前数据量「减半」后计算，所以
n = n / 2 - 逻辑变化的可能性：由于
x是固定的，n会有奇偶数之分，偶数时正好可以平分，直接相乘一半的结果自身即可；奇数时需要把多出来的一个单独乘上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public double power(double x, int n) {
if(n == 0) {
return 1;
}
if(n > 0) {
// divide
// 将大任务分割为两个相同的小任务，但这里更简单只需要递归计算其中一部分即可得到另一部分
double half = power(x, n / 2);
// conquer
if(n % 2 == 0) {
// 如果两个小任务完全相同，则直接乘方
return half * half;
} else {
// 否则需要多乘以x值一次
return half * half * x;
}
} else {
// 负数时先转为正数计算，最终结果求倒数
return 1 / power(x, -n);
}
}
问题转换法
简单来说，一句话就是将x的n次方的结果看成是一个y，这两个其实等价为一个问题
比如2*2和4*1其实是一个问题结果都是4，为了简化计算过程，我们可以将这类「多小值参数相乘」问题转换为「少大值参数相乘」，然后递归处理。
即每次「折半」数量的同时，将参数数值「乘方」，并没有改变问题的描述，仅仅是改变了形式。
思路：
- 首先找到「出口」，由于每次都将问题1化为「等价」的问题2，当问题1只有
1个数字时不需要转化为「等价」的问题2，因为此时两个问题就是一个问题，此时直接返回此时的变量x - 找到参数变化的可能性：每次转换都是将数据量「减半」，所以
n = n / 2，而数据x本身转换为它的「乘方」，所以x = x * x - 逻辑变化的可能性：由于
x是固定的，n会有奇偶数之分，偶数时正好可以继续「完全等价」操作；奇数时需要把本轮进行「等价」转换之后仍然多出来的一个x单独乘上
1
2
3
4
5
6
7
8
9
public double power(double x, int n) {
if(n == 1) // 计算到最里层时只有1个数了直接返回，此时的x是多轮「完全等价」后的结果，即每一轮是上一轮的平方
return x; // 如2的10次方，此时x是三轮「完全等价」结果，第一轮为2的2次方，第二轮为2的4四方，第三轮为2的8次方
if(n % 2 == 0)
return power(x * x, n / 2);
else
return power(x * x, n / 2) * x;
}
for-each法
同样是递归，还有一种慢很多的实现方式，即每次都只乘 x 自己，本质上就是for循环的递归实现。
1
2
3
4
5
6
7
8
9
10
public double power(double x, int n) {
if(n == 0) {
return 1;
}
if(n > 0) {
return x * power(x, n - 1);
} else {
return 1 / power(x, -n);
}
}
这样还不如直接使用 for 循环计算 n 次来的快，它的计算量和 for 是一致的都是 n 次，但是多了额外的 n 次的入栈和出栈操作，
性能上差很多。
迭代
迭代使用循环的方式将递归进行「扁平化」处理，思路：
- 将递归拆解为
while循环，找到「跳出条件」：当前已经没有数字的时候，即个数为0的时候 - 循环内部的计算：每次都要将
n「折半」，将x「乘方」，如果遇到拆分后的个数为奇数时，需要单独将多出来的一个乘到结果里， 剩下的继续在下一轮中参与计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public double power(double x, int n){
if(n == 0)
return 1;
if(n == 1)
return x;
int b = Math.abs(n);
double res = 1.0;
while(b > 0) {
if(b % 2 == 1)
res = res * x;
x = x * x;
// 每次都减少一倍的计算量
b = b / 2;
}
return n > 0 ? res : 1 / res;
}
x的平方根
任何一个数的平方根一定不比它大，0和1除外，并且大概率比它的一半还要小。另外，可能是一个小于1的小数。
如何快速猜到这个数字呢？使用「二分思想」是一个很好的思路，即每次选一个中间的数，如果不满足，可以排除掉一半的候选者，这样的时间复杂度是最优的。
左右边界怎么选？默认最左应该是 0 ，最右侧如果 x 是大于1的整数则是 x 本身，否则是 1.0 ，即小于 1.0 的小数的最右区间。
不断向右和向左调整 low 和 high，使得 mid 的平方不断趋于 x 。
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
def sqrt(x):
if x==0 or x==1:
return x
low = 0
high = max(x, 1.0) # x为小数时，high为1
mid = (low + high)/2.0
while abs(mid**2 - x) > 1e-6: # 误差绝对值满足条件即可退出
if mid**2 > x:
high = mid
else:
low = mid
mid = (low + high)/2.0
return mid
注意这个算法和「二分查找」算法的不同之处，在缩小范围时没有抛出去mid位置的数据，因为这里不是查找具体的位置的数据可以忽略已经判断过 的位置，这里的问题是寻找范围中的某一个值，所以在缩小范围时不会轻易对边界+1或-1，否则可能会因为丢失一部分计算的区间而找不到结果。
与计算x的n次方需要将divide的结果进行conquer不同，这里只需要divide后求出唯一解，无需conquer，称之为decrease and
conquer(Divide and conquer algorithms)，即「减治法」。
Therefore, some authors consider that the name “divide and conquer” should be used only when each problem may generate two or more subproblems. The name “decrease and conquer” has been proposed instead for the single-subproblem class.
分治法主要是将问题分成两个子问题，然后最后将问题合并起来，从而求得其解，减治法是将问题分解，但是没有将解合并，解就在子问题的解中。 通常来说，减治法的效率较高。
References
- https://www.zhihu.com/question/49549135
本文首次发布于 LiuShuo’s Blog, 转载请保留原文链接.
