第十五周：69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

X的平方根肯定会比X小，因此在1~X的范围内用二分查找的方法找到这个数。一开始的时候出现超时，超时代码如下：

int mySqrt(int x) { int mid; int low=0; int high=x; while(high>=low) { mid=(high+low)/2; if(x>mid*mid) low=mid+1; else if(x<mid*mid) high=mid-1; else return mid; } return high; }

我怎么想都解决不了这个问题,知道我将mid定义成Long型，就这样解决问题，这样可以防止mid*mid越界。

AC：

int mySqrt(int x) { long mid; int low=0; int high=x; while(high>=low) { mid=(high+low)/2; if(x>mid*mid) low=mid+1; else if(x<mid*mid) high=mid-1; else return mid; } return high; }