Question:

Implement int sqrt(int x).

Compute and return the square root of x.

Thinking:

We can get the answer using bianry search from the range of integer.

Solution:

public int mySqrt(int x) {
    if ( x <= 1 )
        return x;
    int low = 1;
    int high = Integer.MAX_VALUE;
    while (true){
        int mid = low + (high - low) / 2; //in order to avoid overflow
        if (mid > x / mid){
            high = mid - 1;
        }else{
            if ( (mid+1) > x/(mid+1))
                return mid;
            low = mid + 1;
        }
    }
}