程序设计中平方根怎么表示（leetcodeC题解系列-068）
程序设计中平方根怎么表示（leetcodeC题解系列-068）if (mid <= x / mid) ret = mid; 整个程序非常简单，而且高效 AC:int l = 1 r = x ret = 0; while (l <= r) { int m = (l r) >> 1; if (m <= x / m) { l = m 1; ret = m; } else r = m-1; } return ret; 这道题算是告一段落，但我们其实占了 integer 的便宜，假使要实现的是 float sqrtf(float x) 我们可能需要考虑一下使用著名的牛顿迭代了。这就基本演变为一道数学题了。具体可见 Matrix67 这篇博文中的解释。
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...
由于返回类型是整数，小数部分将被舍去。
解题代码与测试
//
// Created by tannzh on 2020/7/30.
//
/*
* x 的平方根
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4
输出: 2
示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...
由于返回类型是整数，小数部分将被舍去。
*/
#include <iostream>
class Solution {
public:
int mySqrt(int x) {
int l = 1 r = x ret = 0;
while (l <= r) {
int m = (l r) >> 1;
if (m <= x / m) { l = m 1; ret = m; }
else r = m-1;
}
return ret;
}
};
int main(int argc char **argv)
{
Solution s;
std::cout << s.mySqrt(8) << std::endl;
std::cout << s.mySqrt(4) << std::endl;
return 0;
}
解题思路分析
很显然，这又是一道轮子题。有时候我们经常使用某个库函数，的确会偶尔推测它底层是如何实现的。譬如这个 sqrt 它如何做到快准狠？
首先最自然的方案，当然是对对碰。如求 10 的平方根，我可以从 1 开始碰，1*1==1 显然不对，一直到 4*4==16 才发现超出了。于是答案显然是 3.
但这种类似穷举的方式显然很不智，既然是查找能碰对的数，肯定二分搜索要快一些。 如先看 5*5==25 25 > 10 范围向左缩小，并继续中分，有 3*3==9，9 < 10，范围向右缩小，并继续中分，有 4*4==16 16 > 10 right == 3 left == 4. 结束。
那结果应该取哪一次的 middle 呢？显然因为咱们是 integer 的运算，取小不取大，3 可以是结果，4 决计不是。故有：
if (mid <= x / mid) ret = mid;
整个程序非常简单，而且高效 AC:
int l = 1 r = x ret = 0;
while (l <= r) {
int m = (l r) >> 1;
if (m <= x / m) { l = m 1; ret = m; }
else r = m-1;
}
return ret;
这道题算是告一段落，但我们其实占了 integer 的便宜，假使要实现的是 float sqrtf(float x) 我们可能需要考虑一下使用著名的牛顿迭代了。这就基本演变为一道数学题了。具体可见 Matrix67 这篇博文中的解释。
#include <cfloat>
#include <cmath>
float sqrtf(float x) {
float ret;
for (float f = 1.f; true; f = ret) {
ret = (f x / f) / 2;
if (std::abs(f - ret) < FLT_MIN) break;
}
return ret;
}
