x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5

示例 1：

输入：x = 4

输出：2

示例 2：

输入：x = 8

输出：2

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

解题思路

可以从1开始挨个平方，看看那个值的平方与x最为接近，但是这是方式太麻烦了，及其浪费性能和耗费时间。可以使用二分法，我们知道平方根的整数部分是<= x/2的,所以我们在这个范围内做二分查找，找到某个数的平方为x即可

具体步骤如下：

• 第一步：如果X小于2时直接返回X
  
• 第二步：初始化二分法的左右指针，left为1；right为x/2的整数部分
  
• 第三步：当左指针小于等于右指针时进入循环：

• 二分法计算出中间值 mid
• 如果mid的平方等于x就返回mid
• 如果mid的平方小于x就令左指针等于mid+1,否则就令右指针为mid-1

• 第四步：返回 right
  

var mySqrt = function(x) {
    if(x < 2) return x;
    let left = 1;
    let right = Math.floor(x / 2);
    while(left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if(mid * mid === x) return mid;
        if(mid * mid < x){
             left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
};

知识点

• Math.floor(num)仅保留整数部分（向下取整）
• Math.ceil(num)向上取整
• Math.round(num) 四舍五入后的整数
• Math.random() 结果为0-1间的一个随机数(包括0,不包括1)