剑指 Offer II 072. 求平方根(javascript)

一、题目地址

https://leetcode-cn.com/problems/jJ0w9p/

二、具体代码

/**
 * @param {number} x
 * @return {number}
 */
// 二分法
// 时间复杂度: O(nlogn)
// 空间复杂度: O(1)
 var mySqrt = function(x) {
    let left = 1;
    let right = x;
    while(left <= right) {
        let mid = left + ((right - left) >> 1);
        if(mid <= (x / mid)) {
            if((mid + 1) > (x / (mid + 1))) {
                return mid;
            }else {
                left = mid + 1;
            }
        }else {
            right = mid - 1;
        }
    }
    return 0;
};

三、补充思路

1、算法： 二分查找

2、具体思路：对于非负整数 n 可以暴力搜索其正数平方根。具体来讲，从 1 开始，计算当前的值 m 是否满足 m ^ 2 <= n && (m + 1) ^ 2 > n，成立就输出结果，不成立就计算下一个值 m++ 继续判断。暴力解法的时间复杂度为 O(n^0.5)。

这个过程其实可以使用二分法优化，因为根据数学知识可知正数 n 的正数平方根不会大于 n，同时正整数的正数平方根都大于 1。所以数字 n 的平方根一定在区间 [1, n]，取这个区间的中间值 m，并判断 m^2 与 n 的大小关系。

若 m^2 <= n，接着判断 (m + 1)^2 是否大于 n。如果满足 (m + 1)^2 > n，那么 m 就是 n 的平方根。如果满足 (m + 1)^2 <= n，则 n 的平方根比 m 大，继续搜索 [m + 1, n]。

若 m^2 > n，则说明 n 的平方根比 m 小，继续搜索 [1, m - 1]。

使用二分法依次迭代输出结果。

同时，在代码中为了防止整数 int 溢出，在判断 mid * mid <= x 时，均采用 mid <= x / mid 形式，这样可以防止溢出。另外若输入的 n 为 0，因为设置的 left 和 right 初始值为 1 和 n，所以不会进行 while 循环，程序会直接输出 0。

完整代码如下，时间复杂度为 O(logn)。