Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

class Solution {
    int process(int low, int high, int target){
        if (low == high) return low;
        int half = low + (high - low)/2;
        int y = half * half;
        if (y == target) return half;
        if (half <= target/half && low+1!=high) return process(half, high, target);
        else return process(low, half, target);
    }
public:
    int sqrt(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x<=0) return 0;
        return process(1, x, x);
    }
};