69. X 的平方根

给你一个非负整数 X ，计算并返回 X 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(X, 0.5) 或者 X ** 0.5 。

示例1

输入：X = 4
输出：2

示例2

输入：X = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

分析

做题的本质是ac，所以直接一行代码 return (int)Math.sqrt(x);。
分析一下本题，X的平方根其实就是存在于[0-X]这个区间内的一个数，把这个区间看作一个数组，很清楚的发现，这还是一个有序的数组，我们只需要找到一个数Y，满足Y×Y<=X 并且(Y+1)×(Y+1)>X即可

实现

class Solution {
    public int mySqrt(int x) {
        //特殊处理
        if(x<2) return x;
        int left = 0;
        int right = x;
        while(left<right){
            int mid = left+right>>>1;
            //不使用mid*mid 是为了防止溢出
            if(mid>=(x/mid)) right = mid;
            else left = mid +1;
        }
        //为了防止溢出不使用left*left
        return left>x/left?left-1:left;
    }
}