69.x的平方根

1.题目

实现 int sqrt(int x) 函数。

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

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

示例：

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

2.思路

我直接上代码：

public int mySqrt(int x){
    return (int) Math.sqrt(x)
}

hhhh，这样显然是不可以的，人家让自己实现这个函数，调包谁都会。

那么我们来思考一下，如何实现这个函数，首先我们要知道求平方根的特殊情况：0的平方根为0

因为直接返回的是整数部分，所以最简单的思路就是：猜

我们定义二个变量：left、right，用left作为循环的下角标去循环，right=x，我们取left到right的中间值mid，然后用mid的平方与x比较，如果小于x，则将mid的值赋予ans，然后将mid+1赋予left，继续循环。如果大于x，则将mid-1的值赋予right，继续循环。直到left>right的时候，结束循环，返回ans。

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