Java-LeetCode69. 求平方根-二分查找 | 牛顿迭代法

• 算法
  • 二分查找
  • 1.初始范围为1，x
  • 2.当middle*middle <= x && (middle+1)*(middle+1) > x时，返回结果
  • 3.当middle*middle < x时，到右半部分继续寻找
  • 4.当middle*middle > x时，到左半部分继续寻找
  • ps：避免溢出使用逆向运算

public int mySqrt(int x) {
    if (x <= 0) {
        return 0;
    }

    int left = 1, right = x;
    while (true) {
        int middle = (left + right) >> 1;
        if (middle <= x / middle && (middle+1) > x / (middle+1)) {
            return (int) middle;
        } else if (middle < x / middle) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
}

• 算法
  • 牛顿迭代法：``
  • 在这里：``
  • 1.x0 = N
  • 2.x1 = (x0 + N / x0 ) / 2
  • ps：没想到好的的避免溢出方法，直接用long整型

public int mySqrt(int x) {
    if (x <= 0) {
        return 0;
    }

    long r = x;
    while (r > x / r) {
        r = (r + x / r) / 2;
    }
    return (int) r;
}