方法一：二分查找

class Solution {
    public int mySqrt(int x) {
        long l=0,r=x;
        while(l<r)
        {
            //从右向左第一个满足mid*mid<=x的值
            //如果是从左向右的话，只能找第一个mid*mid>=x的值，那么就不是下取整，而是上取整了
            //两个整数相加存在溢出的问题
            long mid=l+r+1>>1;
            if(mid*mid<=x) l=mid;
            else r=mid-1;
        }
        return (int)l;
    }
}

方法二：牛顿迭代法

class Solution {
    public int mySqrt(int x) {
        double cur=x;
        double p=(x+1)/2;
        //利用切线不断逼近的过程中，前者和后者之间的差距小于1e-7就可以跳出循环
        while(Math.abs(p-cur)>1e-7){
            cur=p;
            p=(cur+x/cur)/2;
        }
        return cur>0?(int)cur:-(int)cur;
    }
}