博客

难度：简单

频次：77


题目：给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

解题思路：二分查找

• 二分查找的是开根号值
• 因为可能开根号值是小数，也就是没有相等。所以不能判断先等mid*mid==x
• 去掉小数点，也就是说求的值的平方永远小于真正的开根号值，所以求的mid*mid只能<=x

代码：

class Solution {
    public int mySqrt(int x) {
        int l=0,r=x,res=-1;
        while(l<=r){
            int mid=(l+r)/2;
            //这里mid*mid不能套括号
            //因为只要整数，也就是说我们要得到的值肯定小于真正的开根号
            //只有小于真正的开根号的时候，才算是正确的值，如果超过真正的开根号值，那也就是说错了
            if((long)mid*mid<=x){
                //中间的值还小于X，那就说明X的开根号在右边    
                res=mid;
                l=mid+1;
            }else{
                //也可以在左边
                r=mid-1;
            }
        }
        return res;
    }
}