Intuition#

在 [0, x] 上二分搜尋最大的 r 使得 r*r <= x。

• 本質是找最大的 r 使得 r * r <= x
• 平方函數具有單調性，適合二分搜尋

Approaches#

1: 線性搜尋#

• 概念: 從 0 開始遞增，找到最大的 r 使得 r * r <= x
• 時間複雜度: O(sqrt(x))
• 空間複雜度: O(1)

class Solution {
    fun mySqrt(x: Int): Int {
        var r = 0L
        while ((r + 1) * (r + 1) <= x) {
            r++
        }
        return r.toInt()
    }
}

⭐2: Binary Search#

• 概念: 在 [0, x] 上二分搜尋，找最大的 mid 使得 mid * mid <= x
• 時間複雜度: O(log x)
• 空間複雜度: O(1)

class Solution {
    fun mySqrt(x: Int): Int {
        var left = 0L
        var right = x.toLong()
        while (left < right) {
            val mid = left + (right - left + 1) / 2
            if (mid * mid <= x) {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left.toInt()
    }
}

找最大可行值的二分模板：left = mid 配合向上取整的 mid（加 1 再除 2），避免死迴圈。

3: Newton’s Method#

• 概念: 牛頓法迭代求解 f(r) = r^2 - x = 0，迭代公式 r = (r + x/r) / 2
• 時間複雜度: O(log x)（收斂速度更快）
• 空間複雜度: O(1)

class Solution {
    fun mySqrt(x: Int): Int {
        if (x == 0) return 0
        var r = x.toLong()
        while (r * r > x) {
            r = (r + x / r) / 2
        }
        return r.toInt()
    }
}

🔑 Takeaways#

• Pattern: 在答案空間上二分搜尋最大可行值
• 關鍵技巧: 找最大可行值時 mid 要向上取整；牛頓法是更高效的替代方案但面試中二分搜尋更通用