[LeetCode] 69. Sqrt(x)

Problem : https://leetcode.com/problems/sqrtx/

Use binary search to locate square root in (0, x). 

Since problem statement requests to truncate decimal part, the code needs to return 'right - 1'.  Binary search's 'left' is the lower boundary and 'right' is the upper boundary.

Time complexity : O ( Log(X) )

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