LeetCode Sqrt(x)：二分查找整數平方根防溢出技巧

題目回顧

實現 int sqrt(int x)，返回 √x 的整數部分（向下取整）。

二分查找關鍵：防溢出判斷

搜索範圍 [1, x/2]（x≥2 時 √x ≤ x/2）。
判斷 mid² ≤ x 時不能用 mid * mid（會溢出），改用 mid ≤ x / mid（整除等價）。

C++ 代碼

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int left = 1, right = x / 2, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) { // mid² ≤ x
                ans = mid;        // 記錄候選答案
                left = mid + 1;   // 試探更大值
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
};

牛頓迭代法（更快收斂）

int mySqrt(int x) {
    if (x == 0) return 0;
    double cur = 1, pre = 0;
    while (abs(cur - pre) > 1e-6) {
        pre = cur;
        cur = (cur + x / cur) / 2;
    }
    return (int)cur;
}

運行結果

總結

• 二分法穩健、易於整數邊界控制
• 核心技巧：mid * mid → mid <= x / mid 避免溢出
• 牛頓法收斂快但涉及浮點，面試首推二分