力扣-x的平方根

🔗 题目链接

给你一个非负整数 x ，计算并返回 x 的算术平方根。

由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。

提示：

• $0 <= x <= 2^{31} - 1$

二分查找

参考链接：x 的平方根¹

由于 $x$ 平方根的整数部分 $ans$ 是满足 $k^2 \leq x$ 的最大 $k$ 值，因此我们可以对 $k$ 进行二分查找，从而得到答案。

二分查找的下界为 $0$，上界可以粗略地设定为 $x$。在二分查找的每一步中，我们只需要比较中间元素 $mid$ 的平方与 $x$ 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 $ans$ 后，也就不需要再去尝试 $ans + 1$ 了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def mySqrt(x):
    l, r, ans = 0, x, -1
    while l <= r:
        mid = (l + r) // 2
        if mid * mid <= x:
            ans = mid 
            l = mid + 1
        else:
            r = mid - 1
    return ans

复杂度分析

• 时间复杂度：$O(log⁡x)$，即为二分查找需要的次数。
• 空间复杂度：$O(1)$。