市面上流传着两种二分法的解题模板，这里以二分法求平发根为例子，分析一下它们的区别。
第一种：
# l, r 分别是当前区间的左、右界，m是二分的中间点
while l < r:
m = (l + r + 1) >> 1
if left(m):
r = m - 1
else:
l = m
return l
第二种：
while l < r:
m = (l + r) >> 1
if left(m):
r = m
else:
l = m + 1
return l
left方法判断目标是否在m的左边。
求向下取整的平方根的题目中，left方法可以这么写（注意python中整型的除法是//，两个斜杠）：
# 求x的平方根，这里x是全局变量
def left(m):
return True if x // m < m else False
那么问题来了，求平方根应该用模板一，还是模板二呢？
答案是模板一。
为什么？我们以8的开平方作为例子分析一下。
8的平方根在2和3之间，因此2是正确答案；
假设当m求到了2，这时候精确解是在m的右边的，所以我们取右区间（移动l）；
2是正确答案，显然也需要划分到右边，所以要求 l = m (模板一)；
假设当m求到了3，这时候精确值在左边，取左区间（移动r）；
3肯定不符合要求了，不用划分到左边，所以 r = m - 1（还是模板一）。
也就是说，向下取整要求我们用模板一，每次划分为 [l, m - 1] 和 [m, r] 两个区间；
模板二则划分为 [l, m] 和 [m+1, r]。
两个模板的区别在于把m划分到哪一边。
那么，什么时候该用模板二呢？如果题目要求向上取整，用前面的思路推一遍，可以发现应该用模板二。这时候left也得改一下，大家可以想想为什么。（提示：考虑刚好命中精确解的情况）
网友评论