LeetCode第69题Sqrt(x)：牛顿法实现遇ZeroDivisionError求助

题目描述 #

给定非负整数x，返回x的平方根向下取整后的非负整数。要求不得使用任何内置的指数函数或运算符（例如Python中不能用x ** 0.5）。

示例：

• 输入：x = 4，输出：2（4的平方根是2，直接返回）
• 输入：x = 8，输出：2（8的平方根约2.828，向下取整后返回2）

问题现象 #

使用牛顿迭代法实现时触发ZeroDivisionError，报错位置在语句estimate = (1/2)*(estimate+(x/estimate))。提交的代码如下：

def mySqrt(self, x):
    estimate= 1 + ((x-1)//2)
    difference = abs(x-(estimate*estimate))
    tolerance = .005
    while difference  > tolerance:
        estimate = (1/2)*(estimate+(x/estimate))
        difference  = abs((x-(estimate*estimate)))
    return int(estimate)

报错详情：

Runtime Error
ZeroDivisionError: integer division or modulo by zero
    estimate = (1/2)*(estimate+(x/estimate))
Line 8 in mySqrt (Solution.py)
    ret = Solution().mySqrt(param_1)
Line 29 in _driver (Solution.py)
    _driver()
Line 39 in <module> (Solution.py)

错误原因 #

当输入x=0时，初始estimate的计算过程为：1 + ((0-1)//2) = 1 + (-1) = 0。此时进入循环后执行x/estimate会变成0/0，直接触发除零错误。

修复方案 #

1. 优先处理边界情况：x=0直接返回0，避免初始值计算出现0；
2. 可改用整数版牛顿迭代法，彻底规避浮点数运算的精度问题与除零风险。

修正后的代码 #

方案一：添加边界判断 #

def mySqrt(self, x):
    if x == 0:
        return 0
    if x == 1:
        return 1
    estimate= 1 + ((x-1)//2)
    difference = abs(x-(estimate*estimate))
    tolerance = .005
    while difference > tolerance:
        estimate = (1/2)*(estimate+(x/estimate))
        difference = abs(x - estimate*estimate)
    return int(estimate)

方案二：整数牛顿迭代法（更高效） #

def mySqrt(self, x):
    if x == 0:
        return 0
    estimate = x
    while estimate * estimate > x:
        estimate = (estimate + x // estimate) // 2
    return estimate

该版本全程用整数运算，通过迭代让estimate逐步逼近平方根，当estimate*estimate <=x时停止，返回的estimate即为向下取整的结果。

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