Implement int sqrt(int x).
Compute and return the square root of x.
思路：可以直接用sqrt函数。但实际上这题考察的是二分查找。
代码：
最简单的方法：
1 class Solution { 2 public: 3 int mySqrt(int x) {//1579205274 4 int half=(int)sqrt(x); 5 return half; 6 } 7 };
二分查找：
1 class Solution { 2 public: 3 int mySqrt(int x) {//1579205274 4 if(x<=1){ 5 return x; 6 } 7 int left=1,right=x,mid;//左闭右开 8 while(left<right){ 9 mid=left+(right-left)/2;//直接使用(high + low) / 2 可能导致溢出 10 if(x/mid>=mid){ 11 left=mid+1; 12 } 13 else{ 14 right=mid; 15 } 16 } 17 return left-1; 18 } 19 };
原文：http://www.cnblogs.com/Deribs4/p/5634955.html