69.x的平方根

题目描述

题解

二分查找

这道题可以利用二分法做, 找到平方不超过目标值的最大数字

public int mySqrt(int x) {
    long left = 0;
    long right = x/2+1;

    while (left < right) {
        long mid = (left + right + 1) / 2;
        if (mid * mid > x) {
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    return (int)left;
}

牛顿法

public int mySqrt(int a) {
    long x = a;
    while (x * x > a) {
        x = (x + a / x) / 2;
    }
    return (int) x;
}