求一个整数的算数平方根，输出整数。
解法一：
牛顿迭代法：
// 牛顿法
// f(x) = x^2 - a
// 求解 a 的平方根, 即求解 f(x) = 0 的解
// f(x) ~= f(x0) + (x - x0) * f'(x0);
// 令 f(x) = 0 => x = (x0 + a/x0) /2 => 得到该迭代公式.
class Solution {
public:
int mySqrt( int x ) {
long x0=x; //注意，这里必须是long类型，防止下面x0*x0溢出
while( x0*x0>x ) {
x0 = (x0 + x/x0)/2;
}
return (int)x0;
}
};
解法二： 二分查找
// 二分存在单调性， 存在两段性的性质
// 难点是端点的划分
/*
1、确定边界
2. 二分框架
3. check性质
4. 区间如何更新
5. 更新方式 是l = mid, r = mid - 1 , 计算mid 加上 1
*/
int l = 0, r = x;
while(l < r){
int mid = l + (long long)r + 1 >> 1;
if(mid <= x / mid) l = mid;
else r = mid - 1;
}
return l;
解法三：
代码未解之谜之神奇的0x5f3759df
0x5f375a86来自一个传奇算法(求平方根倒数)，此算法最早被认为是由约翰·卡马克所发明(发明时这个值为0x5f3759df，后来由Lomont通过暴力穷举找到这个更优值)，
class Solution {
public int mySqrt(int x) {
long t = x;
t = 0x5f3759df - (t >> 1);
while (!(t*t <= x && (t+1)*(t+1) > x))
t = (x/t + t)/2;
return (int)t;
}
}
解法四：
// 代码来自《Hacker's Delight》(高效程序的奥秘)一书的第11章.
int mySqrt( int x ) {
unsigned m = 0x40000000, y = 0, b = 0;
while( m != 0 ) {
b = y | m;
y = y >> 1;
if( x >= b ) {
x = x - b;
y = y | m;
}
m = m >> 2;
}
return y;
}