Title:
Implement int sqrt(int x).
Compute and return the square root of x.
思路：这个平方根肯定是在【1，x】之间，所以在这个区间使用二分查找。需要注意的是，代码中一直使用mid ，x/mid来比较，因为如果使用mid的平法，即使long long都会越界
class Solution { public: int mySqrt(int x) { if(x<=1) { return x; } int left = 1; int right = x; while(left<=right) { int mid = (left + right)/2; if(mid == x/mid) { return mid; } else if(mid < x/mid) { left = mid + 1; } else { right = mid - 1; } } return right; } };
原文：http://www.cnblogs.com/yxzfscg/p/4470400.html