学步园

Implement int
sqrt(int x).

Compute and return the square root of x.

»
Solve this problem

经典的二分算法。

class Solution {
private:
    int search(long long l, long long r, long long x) {
        if (l > r) {
            return -1;
        }
        long long mid = (l + r) / 2;
        int q;
        if (mid * mid <= x) {
            q = search(mid + 1, r, x);
            if (q == -1) {
                q = mid;
            }
        }
        else {
            q = search(l, mid - 1, x);
        }
        return q;
    }
    
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return search(0, x, x);
    }
};