Java计算并返回x的平方根（向下取整）

LeetCode

二分法

第一步
设置初始左端点 left = 0 ，右端点 right = x
第二步
求两端点中间的数值 mid = ( left + right ) / 2
第三步
求新的左端点和右端点，并求出新的mid

	if (mid*mid > x){
		right = mid
	}else{
		left = mid
	}
	mid = ( left + right ) / 2

算法

需要使用long类型，int的平方可能会溢出

    public int sqrt(int x) {
    	//首先考虑异常情况
        if (x <= 1) return x;
        //左端点
        long left = 0;
        //右端点
        long right = x;
        //中点
        long mid = 0;
        while (left < right) {
        	//计算mid
            mid = (left + right) / 2;
            //求mid的平方，和mid+1的平方
            if (mid * mid <= x && (mid + 1) * (mid + 1) > x) {
                return (int) mid;
            } else if (mid * mid > x) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return (int) mid;
    }

参考资料

原文链接：https://blog.csdn.net/yu540135101/article/details/114268550