Implementint sqrt(int x).
Compute and return the square root of x.
题意：求根号下x 的值
思路：使用二分搜索。先定义x平方根的取值区间，取值区间不同，在一些细节处理上也是不同的。这里去right为(x/2)+1，这是因为一个非负数x的平方根不大于x/2+1（另外，取right为x见Yu's graden） 。这里值得注意的是，若x的值足够大时，我们取试探值的平方以后会超过INT的类型的范围，所以，我们这里采用除的方式来解决问题，但是这又涉及一个问题，就是，若分母为0时的情况，所以这时应该先讨论x的值。代码如下：
class Solution {
public:
int sqrt(int x)
{
if(x<) return x;
int left=,right=(x/)+;
while(left<=right) //条件和下面right取值的对应
{
int mid=left+(right-left)/;
if(x/mid==mid)
return mid;
else if(x/mid>mid)
left=mid+;
else
right=mid-;
}
return right;
}
};还有一种是牛顿法，参见网友Annie Kim's Blog的博客。代码如下：
class Solution {
public:
int sqrt(int x)
{
if(x==) return ;
double res=,pre=;
while(res !=pre)
{
pre=res;
res=(res+x/res)/;
}
return (int)res;
}
};一个Sqrt函数引发的血案 一文有一个牛掰掰的算法，整体性能提高的不是一点两点。