69 Sqrt(x)

Python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left, right = 0, x
        while left <= right:
            mid = (left + right) // 2
            if mid*mid == x:
                return mid
            elif mid*mid < x:
                left = mid + 1
            else:
                right = mid - 1
        return right

Java

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        if( x == 0 || x == 1)
            return x;
        while (left <= right){
            int mid = left + (right - left)/2;
            if (mid != 0 && mid == x/mid)
                return mid;
            else if (mid < x/mid)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
}