public class Solution {
    public int mySqrt(int x) {
        int l = 0;
        int r = Integer.MAX_VALUE;
        if(x==0)
            return 0;
        while (l<=r){
            int mid = l+(r-l)/2;
            if (mid > x/mid)
                r = mid-1;
            else{
                if (mid+1 >x/(mid+1))
                    return mid;
                l = mid+1;
            }

        }
        return l-1;
    }
}

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l = 0
        r = x

        if x == 0 or x == 1:
            return x
        while l <= r:
            m = (l+r)/2
            if m*m == x:
                return m
            elif m*m < x:
                l = m+1
            else:
                r = m-1
        return l-1