题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

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

示例：

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

思路

1.可以使用二分查找算法，照顾到0和大数就可以了。

Java代码实现

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

Golang代码实现

func mySqrt(a int) int {
    if a<=0{
        return a
    }
    left := 0
    right := a
    for left <= right{
        mid := (left+right)/2
        if mid*mid == a{
            return mid
        }else if mid*mid > a{
            right = mid - 1
        }else{
            left = mid + 1
        }
    }

    return right
}