1 题目描述

给定一个非负整数 x，要求计算并返回 x 的算术平方根的整数部分。需要注意的是，不能使用任何内置的指数函数或运算符来求解该问题。

2 解题思路

本题可以通过二分查找的方法来求解。二分查找是一种在有序数组中查找特定元素的有效算法，对于本题，我们可以通过二分查找的方法在 [0, x] 的范围内寻找满足条件的整数。

1. 初始化：定义两个指针 left 和 right 分别表示搜索区间的起始和结束位置。
2. 循环条件：当 left <= right 时，搜索区间有效，继续执行循环。
3. 中间位置：计算中间位置 mid = left + (right - left) / 2，这样可以避免整数溢出。
4. 比较并更新：
   • 如果 mid * mid <= x，说明 mid 是一个可能的平方根（整数部分），更新 ans = mid 并将搜索区间缩小到 [mid + 1, right]。
   • 如果 mid * mid > x，说明 mid 太大，将其从候选解中排除，更新搜索区间为 [left, mid - 1]。
5. 终止条件：当 left > right 时，退出循环，返回 ans 作为结果。

3 Java 代码实现

public class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int ans = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 使用 long 类型来避免乘法溢出
            if ((long) mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return ans;
    }
}

4 注意事项

• 避免整数溢出：在计算 mid * mid 时，使用 long 类型来存储乘积的结果，以避免整数溢出问题。
• 初始设置：初始设置 right 为 x，这是因为最大可能的平方根不会超过 x。
• 循环条件：循环条件是 left <= right 而不是 left < right，这是因为我们需要包含 left == right 的情况，这可能是目标值所在的单个元素。
• 终止条件：如果退出循环，ans 将会是 x 的最大的整数平方根。