# [Bisect-Upper-Bound]
# https://leetcode.com/problems/sqrtx/
# 69. Sqrt(x)

# History:
# Facebook
# 1.
# May 5, 2019
# 2.
# Apr 4, 2020

# Implement int sqrt(int x).
#
# Compute and return the square root of x, where x is guaranteed to be a
# non-negative integer.
#
# Since the return type is an integer, the decimal digits are truncated and
# only the integer part of the result is returned.
#
# Example 1:
#
# Input: 4
# Output: 2
# Example 2:
#
# Input: 8
# Output: 2
# Explanation: The square root of 8 is 2.82842..., and since
#              the decimal part is truncated, 2 is returned.


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

        while l < r:
            m = l + (r - l) / 2

            m_square = m * m
            if m_square == x:
                return m
            if m_square > x:
                r = m
            else:
                l = m + 1

        return l - 1
