Implementint sqrt(int x).

Compute and return the square root of x.

题意：求根号下x 的值

思路：使用二分搜索。先定义x平方根的取值区间，取值区间不同，在一些细节处理上也是不同的。这里去right为(x/2)+1，这是因为一个非负数x的平方根不大于x/2+1（另外，取right为x见） 。这里值得注意的是，若x的值足够大时，我们取试探值的平方以后会超过INT的类型的范围，所以，我们这里采用除的方式来解决问题，但是这又涉及一个问题，就是，若分母为0时的情况，所以这时应该先讨论x的值。代码如下：

1 class Solution { 2 public: 3     int sqrt(int x)  4     { 5         if(x<2)    return x; 6         int  left=0,right=(x/2)+1; 7         while(left<=right)   //条件和下面right取值的对应 8         { 9             int mid=left+(right-left)/2;10             11             if(x/mid==mid)12                 return mid;13             else if(x/mid>mid)14                 left=mid+1;15             else16                 right=mid-1;17         }    18         return right;    19     }20 };

还有一种是牛顿法，参见网友。代码如下：

1 class Solution { 2 public: 3     int sqrt(int x)  4     { 5         if(x==0)    return 0; 6         double res=1,pre=0; 7         while(res !=pre) 8         { 9             pre=res;10             res=(res+x/res)/2;11         }12         return (int)res;13     }14 };

  一文有一个牛掰掰的算法，整体性能提高的不是一点两点。