69.x的平方根 简单

问题：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

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

示例 1：

输入：x = 4
输出：2

示例 2：

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

回答：

二分查找，降低复杂度

为什么可以用二分查找呢，因为 一个数的算术平方根，基本都会小于它的一半，除了1

left 初始化为0，right初始化为x，通过left <= right的条件进行遍历，求出中间值，中间值相乘如果等于x则直接返回，否则不断收缩左右边界

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