LeetCode - 69. x 的平方根

题目

69. x 的平方根 - 力扣（LeetCode）

思路

初始化搜索范围：

• 对于 x = 0，直接返回 0

• 对于 x > 0，设置 left = 1, right = x

二分查找过程：

• 当 left ≤ right 时循环：

• 计算中点 mid = left + (right - left) / 2

• 比较 mid 与 x/mid 的关系（等价于比较 mid^2 与 x，但避免溢出）

• 如果 mid > x/mid：说明 mid 太大，更新 right = mid - 1

• 如果 mid < x/mid：说明 mid 太小，更新 left = mid + 1

• 如果 mid = x/mid：找到精确平方根，直接返回 mid

处理非完全平方数：

• 循环结束后，right 是小于等于平方根的最大整数

• 返回 right 作为结果

关键技巧

避免整数溢出：

• 使用 mid > x/mid 代替 mid^2 > x

• 这种比较方式数学上等价，但避免了中间结果溢出

边界处理：

• 特殊处理 x = 0 的情况

• 初始化 right = x 而不是 x-1，确保覆盖所有可能值

返回值选择：

• 循环结束时 left > right

• right 指向小于等于平方根的最大整数

• left 指向大于平方根的最小整数

时间和空间复杂度

• 时间复杂度：O(log x)，二分查找的标准复杂度

• 空间复杂度：O(1)，只使用常数额外空间

读者的错误写法

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x-1;

        while(left <= right)
        {
            int mid = left + (right-left)/2;
            if(mid*mid > x)
            {
                right = mid-1;
            }
            else if(mid*mid < x)
            {
                left = mid+1;
            }
            else if(mid*mid == x)
            {
                return left;
            }
        }
        return left;
    }
};

初始化错误：

• right = x-1 可能会导致问题。如果 x = 0，那么 right = -1，这是一个无效的索引。

• 正确的初始化应该是 right = x，因为平方根不会超过 x 本身。

返回值错误：

• 当找到 mid*mid == x 时，你返回的是 left 而不是 mid。

• 应该返回 mid，因为 mid 是满足条件的值。

整数溢出风险：

• 当 x 很大时，mid*mid 可能会导致整数溢出。

• 应该使用 mid <= x/mid 进行比较，避免溢出。

循环结束后的返回值：

• 循环结束后，你返回 left，但此时 left > right，left 指向的是第一个大于平方根的值。

• 应该返回 right，因为 right 指向的是最后一个小于等于平方根的值。

正确写法

class Solution {
public:
    int mySqrt(int x) {
        int left = 1;
        int right = x;

        while(left <= right)
        {
            int mid = left + (right-left)/2;
            if(mid > x/mid)
            {
                right = mid-1;
            }
            else if(mid < x/mid)
            {
                left = mid+1;
            }
            else if(mid == x/mid)
            {
                return mid;
            }
        }
        return right;
    }
};