LeetCode 69题Sqrt(x)实现代码陷入死循环，求排查原因

问题复现 #

实现LeetCode第69题Sqrt(x)时代码陷入死循环，调用print(mySqrt(5))可复现该问题，原代码如下：

def mySqrt(x):
    """
    :type x: int
    :rtype: int
    """
    l, r = 0,x
    result = 0
    while l <= r:
        m = l + ((r-1)//2)
        if m**2 > x:
            r = m - 1 
        elif m**2 < x:
            l = m + 1 
            result = m
        else:
            return m
    return result

问题根源 #

死循环的核心原因是中间值m的计算逻辑错误：
原代码中m = l + ((r-1)//2)的写法不符合二分查找的中间值计算规则，会导致在边界场景下，m的取值无法收敛，l和r始终满足l <= r，触发不了循环终止条件。

以x=5为例，循环后期会进入l=3、r=3的状态：

• 计算m = 3 + ((3-1)//2) = 3 +1 =4
• 4²=16>5，执行r = m-1 =3
• 此时l和r仍为3，循环重复执行上述步骤，陷入无限循环

修正方案 #

将中间值m的计算改为二分查找标准写法，避免溢出的安全写法是m = l + (r - l) // 2，修正后的代码如下：

def mySqrt(x):
    """
    :type x: int
    :rtype: int
    """
    l, r = 0, x
    result = 0
    while l <= r:
        # 修正中间值计算逻辑
        m = l + (r - l) // 2
        if m**2 > x:
            r = m - 1 
        elif m**2 < x:
            l = m + 1 
            result = m
        else:
            return m
    return result

验证 #

调用print(mySqrt(5))会返回2，符合题目要求（5的平方根整数部分为2），且不会出现死循环。

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