Leetcode | Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

线性查找会TLE。用二分查找。注意溢出的处理。全部都改成long long.

class Solution {
public:
    int sqrt(int x) {
        if (x <= 1) return x;
        long long l = 1, r = x / 2 + 1;
        
        while (l <= r) {
            long long m = (l + r) / 2;
            long long v = m * m;
            if (v == x) return m;
            else if (v < x) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        
        return r;
    }
};