方法一

直接进行简单的循环遍历，找到符合条件的值返回结果即可

class Solution {public int mySqrt(int x) {for (int i = 0; i <= x; i++) {if ((long)i * i <= x && (long)(i + 1) * (i + 1) > x) {return i;}}return -1; // 这个返回值实际上不会被触发，因为对于所有正整数 x，总会找到一个 i}
}

二分查找法

class Solution {public int mySqrt(int x) {int left=0,right=x,res=-1;while(left<=right){int mid=left+(right-left)/2;if((long)mid*mid<=x){res=mid;left=mid+1;}else{right=mid-1;}}return res;}
}

详细解析

1. 初始化变量：

   • left 初始化为 0，表示搜索区间的左边界。
   • right 初始化为 x，表示搜索区间的右边界。
   • res 初始化为 -1，用于存储最终的结果。

2. 二分查找循环：

   • 使用 while (left <= right) 循环，直到 left 超过 right 为止。
   • 在每次迭代中，计算中间值 mid：

     int mid = left + (right - left) / 2;
     

     这种计算方式是为了防止 (left + right) / 2 可能导致的整数溢出问题。

3. 检查中间值：

   • 计算 mid * mid 并与 x 进行比较。为了避免整数溢出，将 mid * mid 转换为 long 类型：

     if ((long)mid * mid <= x) {res = mid;left = mid + 1;
     } else {right = mid - 1;
     }
     

   • 如果 mid * mid 小于或等于 x，说明 mid 是一个可能的解，更新 res 为 mid，并将 left 移动到 mid + 1，继续在右半部分查找更大的可能解。
   • 如果 mid * mid 大于 x，说明 mid 太大了，需要在左半部分查找更小的解，因此将 right 移动到 mid - 1。

4. 返回结果：

   • 当 left 超过 right 时，循环结束，此时 res 存储的就是 x 的平方根（向下取整）。