用python写：计算并返回x的平方根整数部分，其中x是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

可以使用二分查找来求解这个问题，算法时间复杂度为O(log n)。具体实现如下：

def mySqrt(x: int) -> int:
    if x == 0:  # 特判
        return 0
    left, right = 1, x  # 左右边界
    while left <= right:
        mid = (left + right) // 2  # 中间值
        if mid * mid == x:  # 如果中间值的平方恰好等于x，直接返回
            return mid
        elif mid * mid < x:  # 如果中间值的平方小于x，更新左边界
            left = mid + 1
        else:  # 如果中间值的平方大于x，更新右边界
            right = mid - 1
    return right  # 返回右边界，即整数部分的值

这里用到了Python的类型注解，可以帮助我们在编写代码时更好地理解参数和返回值的类型。

相关问题

计算并返回x的平方根整数部分，其中x是非负整数。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去

可以使用二分查找来求解。假设答案为ans，那么有0 <= ans <= x。对于ans的值，可以使用二分查找，不断缩小ans的范围，直到找到ans的最大值。

具体实现如下：

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

时间复杂度为O(logx)。

计算并返回x的平方根整数部分，其中x是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

可以使用二分查找来求解。假设要求的数为x，则其平方根的整数部分不会超过x/2+1。因此，可以在0和x/2+1之间进行二分查找，找到最大的整数mid，使得mid的平方不大于x。那么mid就是x的平方根的整数部分。

以下是Python实现：

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

时间复杂度为O(logx)，空间复杂度为O(1)。