题目分析
题目计算int x的平方根，返回值需要是一个非负整型数。
Input: 4
Output: 2
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we want to return an integer, the decimal part will be truncated.
主要思路有两个：第一：二分法查找，寻找平方最接近x的int型；第二：牛顿法进行开方，然后返回int型值。
编程实现
C实现
//binary search
int mySqrt(int x) {
if(x == 0)
{
return 0;
}
int left = 1, right = x;
int mid = (left + right)/2;
while(true)
{
if(x/mid > mid)
{
if((x/mid - mid) == 1)
{
return mid;
}
left = mid;
mid = (left + right)/2;
}else if(x/mid < mid)
{
if((mid - x/mid) == 1)
{
return x/mid;
}
right = mid;
mid = (left + right)/2;
}else
{
return mid;
}
}
}
C++实现
class Solution {
public:
int mySqrt(int x) { //牛顿法求开方
double ans = x;
double delta = 0.0001;
while (fabs(pow(ans, 2) - x) > delta) { //fabs()取浮点型绝对值，pow(a,b)表示a的b次方。
ans = (ans + x / ans) / 2;
}
return ans;
}
};
