Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.

So basically, integer square root is not to compute the exact number of sqrt(x),
but to find the split point where x*x<=target && (x+1)*(x+1)>target
There are 2 ways to do this

1. Binary search

class Solution {
    public int mySqrt(int x) {

        if(x==0) return 0;

        int low = 1;
        int high = Integer.MAX_VALUE;

        while(low<=high){
            int mid=low+(high-low)/2;
            if(mid<=x/mid) {
                if((mid+1)>x/(mid+1)) return mid;
                else low=++mid; 
            }else{
                    high=--mid;
            }
        }

        return -1;

    } 
}

In this solution, the upper bound is initiated to be Integer.MAX_VALUE because the target value may overflow, and mid is caculated as left+(right-left)/2 to avoid overflow.

2. Implement Newton method of Integer Square Root

Time complexity = O(lg(x))
the iterative formula: x_(k+1) = 1/2(x_k + n/x_k), k>=0, x_0>0
Wikipedia

long r = x;
while (r*r > x)
    r = (r + x/r) / 2;
return (int) r;