难度: Easy
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例 1:
输入: x = 4 输出: 2
示例 2:
输入: x = 8 输出: 2 解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
提示:
0 <= x <= 231 - 1注意：本题与主站 69 题相同： https://leetcode-cn.com/problems/sqrtx/
运行时间: 26 ms
内存: 16.1 MB
class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x
while l < r:
mid = (l + r) // 2
if mid * mid >= x:
r = mid
else:
l = mid + 1
return l if l * l == x else l - 1
本题解使用二分查找算法来寻找非负整数 x 的平方根。初始化左边界 l 为 0，右边界 r 为 x。在循环中，计算中间值 mid 为 l 和 r 的平均值。若 mid 的平方大于等于 x，则将右边界 r 更新为 mid，否则将左边界 l 更新为 mid + 1。循环直到左边界小于右边界。最后，如果 l 的平方等于 x，则返回 l，否则返回 l-1，因为此时 l 的平方大于 x 且 (l-1) 的平方小于 x。
时间复杂度: O(log x)
空间复杂度: O(1)
class Solution:
def mySqrt(self, x: int) -> int:
l = 0 # 左边界初始化为0
r = x # 右边界初始化为x
while l < r: # 当左边界小于右边界时持续查找
mid = (l + r) // 2 # 计算中点
if mid * mid >= x: # 如果中点的平方大于等于x
r = mid # 更新右边界为中点
else:
l = mid + 1 # 否则将左边界更新为中点+1
return l if l * l == x else l - 1 # 检查l是否是精确的平方根，否则返回l-1
在二分查找中，`(l + r) // 2`确保了中点mid向下取整，这有助于防止在l和r非常接近时，mid计算结果永远不会超过r，避免了可能的无限循环。另外，这种方式能保证mid永远不会等于r，从而在更新右界时可以直接设置为mid，简化逻辑。使用`(l + r + 1) // 2`可能会导致计算的mid偏大，从而在某些情况下造成错误或效率降低。
在二分查找中，当`mid * mid >= x`时更新右边界为`mid`而不是`mid - 1`是为了保证不错过平方根的正确值。如果`mid * mid == x`，则mid就是我们要找的平方根，如果我们设置`r = mid - 1`，就会错过这个正确值。只有当我们确定`mid * mid > x`时，才知道平方根肯定小于mid，但这个逻辑在判断中已包含，使得代码更加简洁和直观。
本算法在处理非常大的`x`值时性能良好，因为它的时间复杂度为O(log x)，即随着输入值的增大，所需的步骤增长是对数的。对于整数溢出的问题，由于在计算`mid * mid`时可能超出整数范围，Python自动处理大整数，不会发生溢出错误。在其他语言如Java或C++中，可能需要特别处理以避免溢出，例如通过使用长整型或在比较之前检查可能的溢出。