69. Sqrt(x)

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mySqrt(int x) {
        int left = 0, right = x; // [left, right]
        while (left <= right) {
            int mid = (left + right) >>> 1;
            long product = (long)mid * mid;
            if (product < x) {
                left = mid + 1;
            } else if (product > x) {
                right = mid - 1;
            } else {
                return mid;
            } 
        }
        
        // now: right, left
        return right;
    }
}

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        int res = 0;

        int left = 1, right = x; // [left, right]
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (mid < x / mid) {
                res = mid;
                left = mid + 1;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        return res;
    }
}

注意该题不能用左闭右开的方式进行搜索的原因是 left = mid + 1; 收缩区间时会把满足条件的值收缩掉，导致错过结果值。

Binary Search

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }

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

        // now: right, left
        return right;
    }
}

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int mySqrt(int x) {
        // 设 f(t) = t^2 - C, 求 f(t) = 0 时 t 的值
        // 令 t = t0, f(t) 斜率为 2t0, 直线方程为 (y - y0)/(t - t0) = 2t0, 点 (t0, y0) 为 (t0, t0^2 - C)
        // y - (t0^2 - C) = 2t0 * (t - t0)
        // y = 2t0t - 2t0^2 + t0^2 - C = 0
        // 2t0t = t0^2 + C
        // t = (t0^2 + C)/2t0

        // 注意除数不能为 0, 如果为 0, 则 t 为 NaN, 会死循环，所以此处进行特判
        if (x == 0) {
            return 0;
        }

        int C = x;
        double t0 = C;
        while (true) {
            double t = (t0 * t0 + C) / (double) (2 * t0);
            if (t0 - t < 0.000001) {
                return (int) t;
            }

            t0 = t;
        }
    }
}

References

69. Sqrt(x)
剑指 Offer II 072. 求平方根