Square Root (Integer)
你的函数接收一个非负整数 x，并返回它的整数平方根：满足 r × r ≤ x 的最大整数 r。也就是说，结果是向下取整的平方根，因此对于不是完全平方数的数字，结果是小于它的最大完全平方数的平方根。请自己计算，不要使用内置的平方根或幂函数。
函数
- xinteger
- 要进行平方根运算的非负整数
- 返回值integer
- 向下取整到整数的 x 的平方根
约束条件
0 ≤ x ≤ 231 - 1- 不要调用内置的平方根、幂或指数函数。
示例
- 输入
- x = 17
- 输出
- 4
- 解释
4 × 4 = 16不超过 17，但5 × 5 = 25更大，所以 17 的平方根向下取整为 4。
- 输入
- x = 49
- 输出
- 7
- 解释
- 49 是一个完全平方数，
7 × 7 = 49，所以不需要进行舍入，答案正好是 7。
进阶
如果 x 也可能是负数，你会如何改为求整数立方根，也就是满足 r × r × r ≤ x 的最大 r？
提示
逐个打开提示，每个都会多透露一点。
答案是平方不大于
x的最大整数。如果你将某个候选数m平方后与x比较，你能得出哪些比m小和比m大的候选数的信息？随着
m增大，平方也会增大。如果m × m ≤ x，那么所有更小的候选值也都符合条件；如果m × m > x，那么所有更大的候选值都不符合条件。这些候选值按顺序排列，先是符合条件的值，再是不符合条件的值，二分查找可以找到两者的分界点。在 0 和
x之间搜索m。当m × m ≤ x时，记住m并向右搜索；否则向左搜索。用 64 位整数计算m的平方，因为第一个m可能约为10^9。
题解
平方数 0、1、4、9、16 等是有序的，因此你可以通过二分查找，在大约 31 步内找到平方不大于 x 的最后一个数。需要注意的是溢出：候选数的平方并不总能用 32 位表示。
从零开始计数
思路
从 r = 0 开始，当下一个数的平方仍小于或等于 x 时，就递增到 r + 1。循环会在第一个后继数过大的 r 处停止，这就是平方根。对于 x = 17，1、4、9 和 16 的平方都符合条件，而 25 不符合，因此循环会在 4 处停止。
这里最大的平方根是 46340，因此循环最多运行 46340 次。不过，开销会随着输入增大：对于 64 位的 x，可能需要大约 3 × 10^9 步。
算法
- 将
root = 0。 - 当
(root + 1) × (root + 1) ≤ x（使用 64 位整数）时，将root加 1。 - 返回
root。
def mySqrt(x):
root = 0
while (root + 1) * (root + 1) <= x:
root += 1
return root对答案进行二分查找
思路
询问从 0 到 x 的每个候选值，它的平方是否不大于 x。平方只会增大，因此答案在平方根之前都是“是”，之后都是“否”。平方根是最后一个“是”，二分查找通过不断将尚未确定的候选范围减半来找到它。将目前见到的最大“是”保存在 best 中。
当 x = 17 时，查找会依次测试 8（64，太大了）、3（9，符合条件）、5（25，太大了）和 4（16，符合条件）。此时范围为空，best 的值是 4。当 x = 2^31 - 1 时，需要 31 步。
算法
- 设置
lo = 0、hi = x和best = 0。 - 当
lo ≤ hi时，取mid = lo + (hi - lo) / 2。 - 如果
mid × mid ≤ x（使用 64 位整数计算），则设置best = mid和lo = mid + 1。 - 否则，设置
hi = mid - 1。 - 返回
best。
def mySqrt(x):
lo, hi = 0, x
best = 0 # largest candidate seen so far whose square fits
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= x:
best = mid # mid fits, so try a larger root
lo = mid + 1
else:
hi = mid - 1 # mid is too big
return best
易错点和边界情况
- 在 32 位中进行平方运算。对于
x = 2147483647，第一个mid是 1073741823，它的平方约为1.15 × 10^18，会溢出并得到错误的值。请使用 64 位进行乘法，或比较m ≤ x / m。 - 计数循环中也会发生同样的溢出：最后一次检查会计算 46341 的平方，结果为 2147488281，超出了 32 位的范围。
- 使用排他的上界
hi = x + 1。当x是最大的 2147483647 时，x + 1为 2147483648，超出了 32 位的范围。 - 返回最后一次测试的
mid。对于x = 17，搜索在测试 5 后结束；答案是记下的 4。 - 从
lo = 1开始搜索会漏掉x = 0。当m = 0时，检查m ≤ x / m也会导致除以零。
常见问题3
二分查找求平方根的时间复杂度是多少？
时间复杂度为 O(log x)，空间复杂度为 O(1)：每一步都会将范围减半，因此对于 x = 2^31 - 1，需要 31 步。从 0 开始递增需要 O(√x) 步，对于相同的 x，需要 46340 步。
牛顿法如何计算整数平方根？
从 r = x 开始。当 r × r > x 时，使用整数除法将 r 替换为 (r + x / r) / 2。每一步都会让 r 逐渐减小并趋近平方根，但不会小于它，循环会在 r 达到平方根的整数部分时停止。对于 x = 2^31 - 1，需要 19 步。
为什么答案能用 32 位表示，解法却需要使用 64 位整数？
答案最大为 46340，但你测试的候选值并非如此。在 0 到 x 的范围内进行二分查找时，首先会尝试一个接近 10^9 的候选值，它的平方接近 10^18，远超约为 2.1 × 10^9 的 32 位整数上限。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def mySqrt(x):
# 在这里编写代码测试 #1
测试 #2
参数
x = 17
预期输出
4