69.x的平方根
69.1 题目
给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 2^31 - 1
69.2 题解
二分查找法
// 方法一：二分查找法
// 在1-x不断二分查找找到最接近的整数
static int MySqrt1(int x)
{
// 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
if (x == 0 || x == 1)
{
return x;
}
// 初始化左边界为 1，右边界为 x，以及结果变量为 0
long left = 1;
long right = x;
long result = 0;
// 使用二分查找法寻找 x 的平方根
while (left <= right)
{
// 计算中间值 mid
long mid = left + (right - left) / 2;
// 如果 mid 的平方等于 x，直接返回 mid
if (mid * mid == x)
{
return (int)mid;
}
// 如果 mid 的平方小于 x，说明平方根在右半部分，更新左边界和记录结果的变量
else if (mid * mid < x)
{
left = mid + 1;
result = mid; // 记录当前 mid，因为要返回整数部分
}
// 如果 mid 的平方大于 x，说明平方根在左半部分，更新右边界
else
{
right = mid - 1;
}
}
// 返回整数部分结果
return (int)result;
}
牛顿迭代法
// 方法二：牛顿迭代法
// 思路：牛顿迭代法用于逼近方程的根，对于求解平方根问题，迭代公式为 r = (r + x / r) / 2。
// 1. 选择初始值 r 为 x。
// 2. 使用迭代公式逐步逼近 x 的平方根，直到 r * r 不再大于 x。
// 3. 返回整数部分结果，即 r 的整数部分。
static int MySqrt2(int x)
{
// 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
if (x == 0 || x == 1)
{
return x;
}
// 初始化变量 r 为 x
long r = x;
// 使用牛顿迭代法逼近 x 的平方根
while (r * r > x)
{
r = (r + x / r) / 2;
}
// 返回整数部分结果
return (int)r;
}
69.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
// 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
// 注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
// 示例 1：
// 输入：x = 4
// 输出：2
// 示例 2：
// 输入：x = 8
// 输出：2
// 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
// 提示：
// 0 <= x <= 231 - 1
#endregion
#region 测试
// 示例 1
int x1 = 4;
int result1 = MySqrt1(x1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
int result1_2 = MySqrt2(x1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
// 示例 2
int x2 = 8;
int result2 = MySqrt1(x2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
int result2_2 = MySqrt2(x2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
#endregion
}
#region 答案
// 方法一：二分查找法
// 在1-x不断二分查找找到最接近的整数
static int MySqrt1(int x)
{
// 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
if (x == 0 || x == 1)
{
return x;
}
// 初始化左边界为 1，右边界为 x，以及结果变量为 0
long left = 1;
long right = x;
long result = 0;
// 使用二分查找法寻找 x 的平方根
while (left <= right)
{
// 计算中间值 mid
long mid = left + (right - left) / 2;
// 如果 mid 的平方等于 x，直接返回 mid
if (mid * mid == x)
{
return (int)mid;
}
// 如果 mid 的平方小于 x，说明平方根在右半部分，更新左边界和记录结果的变量
else if (mid * mid < x)
{
left = mid + 1;
result = mid; // 记录当前 mid，因为要返回整数部分
}
// 如果 mid 的平方大于 x，说明平方根在左半部分，更新右边界
else
{
right = mid - 1;
}
}
// 返回整数部分结果
return (int)result;
}
// 方法二：牛顿迭代法
// 思路：牛顿迭代法用于逼近方程的根，对于求解平方根问题，迭代公式为 r = (r + x / r) / 2。
// 1. 选择初始值 r 为 x。
// 2. 使用迭代公式逐步逼近 x 的平方根，直到 r * r 不再大于 x。
// 3. 返回整数部分结果，即 r 的整数部分。
static int MySqrt2(int x)
{
// 如果 x 等于 0 或 1，直接返回 x，因为其平方根为自身
if (x == 0 || x == 1)
{
return x;
}
// 初始化变量 r 为 x
long r = x;
// 使用牛顿迭代法逼近 x 的平方根
while (r * r > x)
{
r = (r + x / r) / 2;
}
// 返回整数部分结果
return (int)r;
}
#endregion
}
69.4 运行结果
示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：2
示例2 方法2 输出：2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
