市面上流传着两种二分法的解题模板,这里以二分法求平发根为例子,分析一下它们的区别。
第一种:
# 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也得改一下,大家可以想想为什么。(提示:考虑刚好命中精确解的情况)