一、题目

二、实验代码

//解法一
class Solution {
    public int mySqrt(int x) {
       double y=Math.sqrt(x);//调用库函数Math.sqrt(),其返回值类型为double
       return (int)(y);//将double类型强转转换成int类型
    }
}


//解法二
class Solution {
    public int mySqrt(int x) {
       if(x<0)//当x<0时抛出异常 RuntimeException(RuntimeException是java中所有运行时异常的父类，实际运行时出现的都是它的子类)
       {
           throw new RuntimeException("求平方根的数不能为负数");
       }
           if(x==1||x==0)//0和1开平方为其本身
           {
               return x;
           }
           int left=0,right=x;//本题中left可以为1,进行(right+left)/2+1后将double类型强制成int类型
           while(left<right)
           {
               int mid=(right+left)/2+1;//平方根向下取整的值，若取值的平方大于给定的数，需要向左减1;若小于给定的数，左界限变为我们所需要的平方值
               if(mid>x/mid)//对于不是完全平方数的数值,若平方值大于x，则这个数一定是大于平方根的整数，中间值向左移一位赋值给右侧即right=mid-1
               {
                   right=mid-1;
               }
               else//若平方值小于x，则这个数一定是小于平方根到底整数，直接将中间值赋值给左侧，left=mid
               {
                   left=mid;
               }
           }
       return left;
    }
}

三、运行情况
解法一：

解法二：

四、刷题总结
我们在本题前，需要明确的是，所求的平方根是向下取整，对于方法一，向下取整有两种方法，直接使用int强转，或者使用Math.floor()，但直接调用库函数在真正的面试中不会考察，仅供参考；对于方法二，因为 x的平方根的整数部分是满足k*k<=x的最大整数值，可以对k进行二分查找。令二分查找的下界为0，上界为x(所求平方根的数),在二分查找的每一步中，我们只需要比较中间元素的平方与x的大小关系，并通过比较结果调整上下界的范围， 且我们所有的运算都是整数运算，不会存在误差。

Java编程之二分法查找(折半查找)：https://blog.csdn.net/qq_44111805/article/details/109958010