69 Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

class Solution {
public:
    int sqrt(int x) {
        if (x<=1)
            return x;
         return help(x,1,x/2);
    }
    int help(int x, int low,int high)
    {
        if (low>high)
            return high + (low-high)/2;
        double mid = (double) low + (high-low)/2;
        if (mid==x/mid)
            return mid;
        if (mid>x/mid)
            return help(x,low,mid-1);
        return help(x,mid+1,high);
    }
};