69.x的平方根
69. x 的平方根
069. x 的平方根
题意
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
难度
简单
示例
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
分析
法 1.牛顿迭代法
牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson
method），它是牛顿在 17 世纪提出的一种在实数域和复数域上近似求解方程的方法。
但是这题并不需要我们去了解复数域上求解方程的过程。
我们只需要把$ x^2=C $这个方程解出来即可。
首先我们令$ f(x)=x^2-C ， 再 取 一 个 x_0 。（ 下 文 中 以 f(x)=x^2-4 $为例）
1673257443733-6dbe8334-31cb-4530-880c-216ccf335eb9.png
如果$ x_0 并 非 f(x)=0 的 解 ， 那 我 们 就 在 (x_0,f(x_0)) 处 ， 做 f(x) $的切线
1673257452279-42fa40ca-fe4b-4dd2-a7fd-91584ef86e77.png
接着，再取$ x_1=2.5 ， 这 时 候 f(x_1)=2.25 ，发 现 (x_1,f(x_1)) 仍 然 不 是 f(x)=0
$的解。
于是我们继续在$ (x_1,f(x_1)) 处 做 f(x) $的切线，从而得到：
1673257459525-1c54377d-1068-4394-8632-1cb1be30949f.png
这时候切线与 x 轴的交点为$ 2.05
，已 经 很 接 近 我 们 的 答 案 了 。 可 以 看 得 出 ， 只 要 不 断 重 复 — — “ 取 点 ， 做 切 线
x_i 是 否 为 f(x)=0 的 解 ， 有 两 种 方 法 ，一 个 是 判 断 f(x_i)
是 否 为 0 ，另 一 个 则 是 判 断 x_i 和 x_{i-1} $是否无限接近。
class Solution {
public int mySqrt(int x){
if(x == 0 || x == 1)
return x;
double res = x;
double lastVal = 0;
do{
lastVal = res;
res = res / 2.0 + x / 2.0 / res;
}while(Math.abs(res - lastVal) > 1e-7);
return (int)res;
}
}
执行效率如下：
1673257467211-c3f684ee-d169-47f8-bac3-9d1d31c9e930.png
法 2.二分搜索
对于一个非负数$ n ， 它 的 平 方 根 不 会 大 于 n/2+1 $，证明过程如下：
设$ f(x)=(n/2 + 1) - $
它的最小值为$ f(1)=0.5 ， 所 以 f(x)>=0.5 $
所以$ f(x)>0 $ ，即$ n/2 + 1 > $
故我们可以在$ [0,n/2+1] 这 个 范 围 内 进 行 二 分 搜 索 ， 也 一 样 可 以 得 到
$。
class Solution {
public int mySqrt(int x) {
if(x == 0 || x == 1)
return x;
int lef = 0,rig = x/2 + 1;
int res = -1;
while(lef <= rig){
int mid = (lef + rig) >> 1;
if(mid <= x / mid){
lef = mid + 1;
res = mid;
} else
rig = mid - 1;
}
return res;
}
}
执行效率如下：
1673257474678-eca2e5a0-555d-4008-b9ef-fecd09ec0e20.png
总结
对于求$ x
平 方 根 这 种 题 型 ，我 们 可 以 采 用 多 种 方 法 ，甚 至 可 以 利 用 穷 举 ，依 次 从
0-x $来枚举，在穷举之上我们利用做差法来证明 $ n 的 平 方 根 不 会 大 于 n/2+1
， 从 而 更 快 求 解 出 $，或者再进一步利用牛顿迭代法……
力扣链接：https://leetcode.cn/problems/sqrtx/