def my_sqrt(x: int) -> int:
    """Implement int sqrt(int x)
    https://leetcode.com/problems/sqrtx/

    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.
    """
    if x == 0:
        return 0
    if x < 4:
        return 1

    left = 2
    right = x

    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid ** 2 < x:
            left = mid + 1
        else:
            right = mid - 1

    return left - 1