一、题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
二、解题思路 & 代码
2.1 二分法
**思路分析：**使用二分法搜索平方根的思想很简单，就类似于小时候我们看的电视节目中的“猜价格”游戏，高了就往低了猜，低了就往高了猜，范围越来越小。因此，使用二分法猜算术平方根就很自然。
一个数的平方根肯定不会超过它自己，不过直觉还告诉我们，一个数的平方根最多不会超过它的一半，例如 8 的平方根，8 的一半是 4， 4 2 = 16 > 8 4^2=16>8 42=16>8，如果这个数越大越是如此，因此我们要计算一下，这个边界是多少。为此，解如下不等式：
( a 2 ) 2 ≥ a \left(\frac{a}{2}\right)^{2} \geq a (2a)2≥a
意即：如果一个数的一半的平方大于它自己，那么这个数的取值范围。解以上不等式得 a ≥ 4 a≥4 a≥4 或者 a ≤ 0 a≤0 a≤0。
于是边界值就是 4，那么对 0、1、2、3 分别计算结果，很容易知道，这 4 个数的平方根依次是 0、1、1、1。
注意：这 4 个特值如果没有考虑到，有可能导致你设置的搜索边界不正确。在使用二分法寻找平方根的时候，要特别注意边界值的选择
class Solution:
def mySqrt(self, x: int) -> int:
l = 0
r = x
while l <= r:
mid = (l+r)//2
temp = mid**2
if temp < x:
l = mid + 1
elif temp > x:
r = mid - 1
elif temp == x:
return mid
# r一定会停在mid**2 <= x的最大那个mid的位置，因为mid**2=x的mid如果存在的话在上面
# 就已经返回了，所以这里只需要返回r就好了
return r
复杂度分析：
时间复杂度：O(logN)，二分法的时间复杂度是对数级别的。
空间复杂度：O(1)，使用了常数个数的辅助空间用于存储和比较。
2.2 牛顿法
使用牛顿法可以得到一个正实数的算术平方根，因为题目中说“结果只保留整数部分”，因此，我们把使用牛顿法得到的浮点数转换为整数即可。
牛顿法的思想：
在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 x 轴的交点，重复这个过程直到收敛。
注意：牛顿法得到的是平方根的浮点型精确值（可能会有一定误差），根据题目中的要求，把最后得到的这个数转换为 int 型，即去掉小数部分即可。
class Solution:
def mySqrt(self, x):
if x < 0:
raise Exception('不能输入负数')
if x == 0:
return 0
# 起始的时候在 1 ，这可以比较随意设置
cur = 1
while True:
pre = cur
cur = (cur + x / cur) / 2
if abs(cur - pre) < 1e-6:
return int(cur)
京公网安备 11010502036488号