Poison

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;
        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;
    }
}
Binary Search
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) {
        if (x <= 1) {
            return x;
        }

        int left = 0, right = x / 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2; // 向右取整，如 left = 1, right = 2 时，若不向上取整，则会使 left 被赋值为自身，导致死循环
            if (mid <= x / mid) {
                left = mid; // 此时 mid 可能为答案，不能加 1, 下一轮搜索区间为：[mid, right]
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}
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;
        }
    }
}
Reference

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