069. x 的平方根

作者：沉默王二
发布时间：2023-01-09T17:47:15.007+0800

---

题意

**
**本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

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

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

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

难度

简单

示例

示例 1：

输入：x = 4

示例 2：

输入：x = 8

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

分析

法1.牛顿迭代法

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

但是这题并不需要我们去了解复数域上求解方程的过程。

我们只需要把这个方程解出来即可。

首先我们令，再取一个。（下文中以为例）

如果并非的解，那我们就在处，做的切线

接着，再取，这时候，发现仍然不是的解。

于是我们继续在处做的切线，从而得到：

这时候切线与x轴的交点为，已经很接近我们的答案了。可以看得出，只要不断重复——“取点，做切线，取切线与x轴交点“这个过程，我们就能逼近方程的解，这就是牛顿迭代法，而牛顿迭代法判断是否为的解，有两种方法，一个是判断是否为0，另一个则是判断和是否无限接近。

class Solution { 

  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;  } }

执行效率如下：

法2.二分搜索

对于一个非负数，它的平方根不会大于，证明过程如下：

设

它的最小值为，所以

所以 ，即

故我们可以在这个范围内进行二分搜索，也一样可以得到。

class Solution { 

  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;  } }

执行效率如下：

总结

对于求平方根这种题型，我们可以采用多种方法，甚至可以利用穷举，依次从来枚举，在穷举之上我们利用做差法来证明 的平方根不会大于，从而更快求解出，或者再进一步利用牛顿迭代法……

力扣链接：https://leetcode.cn/problems/sqrtx/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

**
**本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

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

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

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

难度

简单

示例

示例 1：

输入：x = 4

示例 2：

输入：x = 8

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

分析

法1.牛顿迭代法

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

但是这题并不需要我们去了解复数域上求解方程的过程。

我们只需要把这个方程解出来即可。

首先我们令，再取一个。（下文中以为例）

如果并非的解，那我们就在处，做的切线

接着，再取，这时候，发现仍然不是的解。

于是我们继续在处做的切线，从而得到：

这时候切线与x轴的交点为，已经很接近我们的答案了。可以看得出，只要不断重复——“取点，做切线，取切线与x轴交点“这个过程，我们就能逼近方程的解，这就是牛顿迭代法，而牛顿迭代法判断是否为的解，有两种方法，一个是判断是否为0，另一个则是判断和是否无限接近。

class Solution { 

  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;  } }

执行效率如下：

法2.二分搜索

对于一个非负数，它的平方根不会大于，证明过程如下：

设

它的最小值为，所以

所以 ，即

故我们可以在这个范围内进行二分搜索，也一样可以得到。

class Solution { 

  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;  } }

执行效率如下：

总结

对于求平方根这种题型，我们可以采用多种方法，甚至可以利用穷举，依次从来枚举，在穷举之上我们利用做差法来证明 的平方根不会大于，从而更快求解出，或者再进一步利用牛顿迭代法……

力扣链接：https://leetcode.cn/problems/sqrtx/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

题意

**
**本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

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

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

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

难度

简单

示例

示例 1：

输入：x = 4

示例 2：

输入：x = 8

解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

分析

法1.牛顿迭代法

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

但是这题并不需要我们去了解复数域上求解方程的过程。

我们只需要把这个方程解出来即可。

首先我们令，再取一个。（下文中以为例）

如果并非的解，那我们就在处，做的切线

接着，再取，这时候，发现仍然不是的解。

于是我们继续在处做的切线，从而得到：

这时候切线与x轴的交点为，已经很接近我们的答案了。可以看得出，只要不断重复——“取点，做切线，取切线与x轴交点“这个过程，我们就能逼近方程的解，这就是牛顿迭代法，而牛顿迭代法判断是否为的解，有两种方法，一个是判断是否为0，另一个则是判断和是否无限接近。

class Solution { 

  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;  } }

执行效率如下：

法2.二分搜索

对于一个非负数，它的平方根不会大于，证明过程如下：

设

它的最小值为，所以

所以 ，即

故我们可以在这个范围内进行二分搜索，也一样可以得到。

class Solution { 

  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;  } }

执行效率如下：

总结

对于求平方根这种题型，我们可以采用多种方法，甚至可以利用穷举，依次从来枚举，在穷举之上我们利用做差法来证明 的平方根不会大于，从而更快求解出，或者再进一步利用牛顿迭代法……

力扣链接：https://leetcode.cn/problems/sqrtx/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1300 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412