我关于Sqrt（x）的解决方案有什么问题

Question

测试代码的网页如下： https://leetcode.com/problems/sqrtx/description/

我交了这些代码并通过了：

class Solution(object):
def mySqrt(self, x):
    """
    :type x: int
    :rtype: int
    """
    if x==1:
        return 1
    lowest=0.0
    uppest=x*1.0
    count=1
    middle=(lowest+uppest)*0.5
    while (abs(middle*middle-x)>0.001) and (count<=10000):
        if middle*middle>x:
            uppest=middle
        else:
            lowest=middle
        middle=(lowest+uppest)*0.5
        count=count+1
    return int(middle)

但当我改变时

while (abs(middle*middle-x)>0.001) and (count<=10000):

进入

while (abs(middle*middle-x)>0.0001) and (count<=10000):

或添加更多“0”，如0.00000000001，并使用“9”作为输入进行测试，则会出错输出应该是3，但我得到了2

在使用对分法时，如何解决这类问题？ 我不想使用图书馆（我知道使用图书馆是最简单的方法，但我想了解更多）

Answer 1

罪魁祸首是

return int(middle)

获得2的原因是将2.99998855591这样的数字强制转换为int，这相当于floor(x)

在多次迭代n0之后，目标值和中间值之间的误差sqrt(x) - middle遵循阻尼振荡。你知道吗

取而代之的是四舍五入到最接近的整数 回程（中间）

Answer 2

看看其他的答案。解决方案是：

return int(middle + 0.5)

向最接近的整数舍入。你知道吗

当然，更大的问题是，在计算整数平方根时，要将中间值转换为浮点值。与Python int相比，float的范围非常有限。请尝试以下操作：

def int_sqrt(n):
    """Return integer square root of integer ``n``.
    """
    x = n
    y = (x + 1) >> 1
    while y < x:
        x = y
        y = (x + n // x) >> 1
    return x

例如，在int_sqrt(2**12345-1)上运行它，它应该返回一个1858位的数字。你知道吗

Answer 3

它更像是一道数学题而不是python，只需插入

print(middle,middle**2>x)

用于调试目的。你知道吗

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x==1:
            return 1
        lowest=0.0
        uppest=x*1.0
        count=1
        middle=(lowest+uppest)*0.5
        while (abs(middle*middle-x)>0.0001) and (count<=10000):
            if middle*middle>x:
                uppest=middle
            else:
                lowest=middle
            middle=(lowest+uppest)*0.5
            count=count+1
            print(middle,middle**2>x)
        return int(middle)

sol=Solution()
print(sol.mySqrt(9))

输出

2.25 False
3.375 True
2.8125 False
3.09375 True
2.953125 False
3.0234375 True
2.98828125 False
3.005859375 True
2.9970703125 False
3.00146484375 True
2.999267578125 False
3.0003662109375 True
2.99981689453125 False
3.000091552734375 True
2.9999542236328125 False
3.0000228881835938 True
2.999988555908203 False
2

你已经知道原因了。你知道吗

我也想知道为什么你不能用

round(middle)