难度: Easy
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4 输出：2
示例 2：
输入：x = 8 输出：2 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
Submission
运行时间: 44 ms
内存: 14.5 MB
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
if x <= 3:
return 1
l = 2
r = x // 2 + 1
while l < r:
mid = l + (r - l + 1) // 2
if mid * mid <= x:
l = mid
else:
r = mid - 1
return l
Explain
这个题解使用了二分查找的方法来寻找平方根。首先判断一些特殊情况，如果 x 等于 0 就直接返回 0；如果 x 小于等于 3，平方根一定是 1。对于其他情况，使用两个指针 l 和 r 分别指向搜索区间的左右边界。每次取区间的中点 mid，判断 mid 的平方是否小于等于 x。如果是，说明平方根可能在右半区间，将左指针移到 mid；否则平方根在左半区间，将右指针移到 mid-1。当左右指针相遇时，找到平方根的整数部分。
时间复杂度: O(log x)
空间复杂度: O(1)
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
if x <= 3:
return 1
l = 2
r = x // 2 + 1
while l < r:
mid = l + (r - l + 1) // 2
if mid * mid <= x: # 如果 mid 平方小于等于 x，说明平方根在右半区间
l = mid
else: # 否则平方根在左半区间
r = mid - 1
return l # 当左右指针相遇时，找到平方根的整数部分
Explore
在二分查找中使用 `mid = l + (r - l + 1) // 2` 是为了确保在迭代过程中中点 `mid` 能够向上取整。这种做法主要用于避免在某些情况下可能出现的死循环，特别是当 `l` 和 `r` 很接近时。如果使用 `mid = l + (r - l) // 2`，则 `mid` 向下取整，可能导致在特定条件下 `l` 和 `r` 更新后仍然不变，从而陷入死循环。使用向上取整的方法可以保证区间能够有效缩小，进而使算法正确地收敛到解。
当 `mid * mid <= x` 成立时，选择将左指针 `l` 更新为 `mid` 而不是 `mid + 1` 是为了确保不错过可能的正确答案。在二分查找中寻找平方根的场景中，如果 `mid` 的平方小于或等于 `x`，则 `mid` 可能是正确答案或更小的值可能是正确答案，因此需要保持 `mid` 在搜索范围内。如果更新为 `mid + 1`，可能会错过正确的平方根值。
对于 `x <= 3` 直接返回 1 的原因是基于整数的平方根的定义。整数的平方根是求不超过根号下的最大整数。对于 `x = 1`，平方根为 1；对于 `x = 2` 和 `x = 3`，它们的平方根也是 1，因为根号下 2 和 3 的实际值介于 1 和 2 之间，但我们需要返回不超过这个实际值的最大整数，即 1。因此，对这三个数，返回 1 是准确的。
在二分查找结束时返回 `l` 是因为 `l` 和 `r` 在查找结束时会合并在正确的答案上。由于更新指针的逻辑（即左指针向右移动到 `mid`，右指针向左移动到 `mid-1`），`l` 和 `r` 最终都会指向同一个位置，这个位置是满足条件的最大可能的整数。返回 `l` 或 `r` 都是可以的，因为它们是相等的；而返回 `mid` 则不可行，因为在循环结束时，`mid` 可能并不等于 `l` 或 `r`。