为何两个平方根二分查找算法的迭代次数差异如此巨大？

嘿，我来帮你拆解一下这个问题！你提到自己实现的平方根算法和课程示例都是想做二分查找，但迭代次数差了好几个数量级，核心原因是你的代码并没有真正实现二分查找的逻辑，咱们一步步来看：

你的实现代码 #

def ssqrt(x):
    origx = x
    epsilon = 0.000001
    num_guess = 0
    while abs((x/2)**2 - origx) >= epsilon:
        #print(x)
        num_guess+=1
        if (x/2)**2 >= origx:
            x = x/2
        elif (x/2)**2 <= origx:
            x = (3/2)*x
    if abs((x/2)**2 - origx) < epsilon:
        print(num_guess)
        return x/2
y = ssqrt(49)
print(y)

课程示例代码 #

x = 49
low = 0
high = x
ans = (low+high)/2
epsilon = 0.00000000000001
num = 0
while abs(ans**2-x) >= epsilon:
    num += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high+low)/2
print (num)
print (ans)

核心差异分析 #

1. 示例代码是标准二分查找 #

示例代码的逻辑非常清晰：

• 一开始就明确了搜索区间：low=0（平方根的最小可能值）和high=x（平方根的最大可能值，当x>=1时）
• 每次取区间的中间值ans=(low+high)/2，通过比较ans²和目标值x的大小，直接把区间砍掉一半：如果ans² < x，说明平方根在[ans, high]区间，就把low移到ans；反之则把high移到ans
• 这种每次减半区间的方式，收敛速度是对数级的，比如找49的平方根，只需要log2(49/epsilon)次迭代，几十次就足够达到极高精度

2. 你的代码是“伪二分”，收敛效率极低 #

你的代码看起来像是在调整数值，但本质没有维护一个明确的搜索区间：

• 你只用了一个变量x来调整，每次要么把x减半，要么乘以1.5
• 当计算49时，一开始x=49，x/2=24.5的平方远大于49，所以不断把x减半，直到x/2的平方小于49，这时候你又把x变成3x/2，导致x/2的平方又可能大于49，于是又要开始减半——这种来回震荡的调整方式，每次只能非常缓慢地逼近目标值，需要几百万次迭代才能收敛到epsilon范围内
• 简单来说，你没有利用“平方根一定在0到x之间”这个明确的区间范围，而是在盲目地缩放单一变量，完全没有发挥二分查找“每次砍半区间”的高效特性

总结 #

如果想让你的代码达到示例的效率，需要改成维护low和high两个边界的标准二分查找逻辑，而不是通过单一变量的缩放来试探。这样就能把迭代次数从几百万次降到几十次啦！

内容的提问来源于stack exchange，提问作者Abhigyan