Swift中不使用内置函数计算整数平方根遇超时问题求助

问题根源 #

你的代码出现超时的核心原因是整数除法导致牛顿迭代逻辑陷入无限循环。Swift中Int类型的/是截断式整数除法，会直接丢弃小数部分，彻底破坏了牛顿迭代的收敛性。

拿输入x=8的情况举例，迭代过程会卡在循环里无法退出：

• 初始y=8，x/y=8/8=1，z=(8+1)/2=4（整数除法，9÷2=4）
• 下一轮y=4，x/y=8/4=2，z=(4+2)/2=3
• 再下一轮y=3，x/y=8/3=2（整数除法截断为2），z=(3+2)/2=2
• 再下一轮y=2，x/y=8/2=4，z=(2+4)/2=3
• 从此y和z在3、2之间来回切换，abs(y-z)永远等于1，远大于设定的阈值0.00001，循环永远无法终止，最终超时。

修复方案 #

方案1：改用浮点型迭代（修正牛顿法） #

将变量类型改为浮点型，确保除法是浮点除法，让迭代能正常收敛：

func mySqrt(_ x: Int) -> Int {
    if x < 2 { return x }
    
    var y = Double(x)
    var z = (y + Double(x)/y) / 2

    while abs(y - z) >= 0.00001 {
      y = z
      z = (y + Double(x)/y) / 2
    }
    
    return Int(z)
}

方案2：改用二分查找法（更适合整数场景） #

如果追求整数运算的高效性，避免浮点转换的开销，推荐用二分查找实现，逻辑更稳定且不会出现循环陷阱：

func mySqrt(_ x: Int) -> Int {
    if x < 2 { return x }
    var left = 1, right = x / 2
    var result = 0
    while left <= right {
        let mid = left + (right - left) / 2
        // 用除法判断避免mid*mid溢出
        if mid <= x / mid {
            result = mid
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return result
}

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