Implement int sqrt(int x).
Compute and return the square root of x.
Subscribe to see which companies asked this question
解法1：使用求正数的平方根的一般二分查找法：
class Solution { public: int mySqrt(int x) { if(x == 0 || x == 1) return x; double limit = 0.000001; double left = 0, right = x, mid = (left + right) / 2.0; double dist = x - mid * mid; while (abs(dist) > limit) { if (dist > limit) left = mid; else right = mid; mid = (left + right) / 2.0; dist = x - mid * mid; } return mid; } };
解法2：因为输出为int型，实际并不需要精确求出x的实际平方根，因此可以改进：
class Solution { public: int mySqrt(int x) { long long left = 0, right = x; while (left <= right) { long long mid = (left + right) / 2; long long sqrt = mid * mid; if (sqrt == x) return mid; else if (sqrt > x) right = mid - 1; else left = mid + 1; } return right; //注意若无精确值，则返回略小于其平方根的那个 } };
解法3：可以使用牛顿迭代法求f(x)=0的根，而求n的平方根相当于求解方程f(x)=x^2-n=0的根，所以可以使用此方法。
设r是
的根，选取
作为r的初始近似值，过点 
做曲线 
的切线L，L的方程为 
，求出L与x轴交点的横坐标 
，称x1为r的一次近似值。过点 
做曲线 的切线，并求该切线与x轴交点的横坐标 
，称 
为r的二次近似值。重复以上过程，得r的近似值序列，其中， 
称为r的 
次近似值。
将上面公式应用到方程f(x)=x^2-n=0即可得到公式：
一般取初始值x0=1。
class Solution { public: int mySqrt(int x) { double limit = 0.000001, root = 1.0; while (abs(x - root * root) > limit) root = (root + x / root) / 2.0; return root; } };
原文：http://www.cnblogs.com/aprilcheny/p/4957370.html