使用max()函数的二分查找

Question

我们为什么要使用max函数呢？难道我们不能直接把high的值赋给x吗？那样也能达到我们的目的。那么，使用max()函数对算法有什么好处呢？

x=25
epsilon=0.01
numGuesses= 0
low =0.0
high = max(1.0,x)
ans = (high+low)/ 2.0
while abs(ans**2 -x)>= epsilon:
    print 'low =', low, 'high =', high, 'ans =', ans
    numGuesses+= 1
    if ans**2 <= x:
        low= ans
    else:
        high= ans
    ans = (high+low)/2.0
print 'numGuesses =', numGuesses
print ans, 'is close to square root of', x

Answer 1

这段代码的目的是为了计算任何一个 x 值的平方根，而不仅仅是25的平方根。我们通过设置一个 low 值和一个 high 值，这两个值分别比平方根小和大，然后通过数学运算让它们更接近正确的平方根值。

当 x 在0到1之间时，x 的平方根会大于 x 本身。因此，我们不能把 high 设置为 x，因为它需要比我们想要的答案大。但是在这种情况下，我们也知道 x 的平方根会小于1，所以1可以作为初始的 high 值。（同样地，当 x 大于1时，x 的平方根也会大于1，但会小于 x。）