Description:
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example 1:
Input: 4 Output: 2
Example 2:
Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
解法一：
一开始没有明白题目的用途，直接调用sqrt函数之后，强制转换成int类型。代码如下：
class Solution { public: int mySqrt(int x) { double tmp; tmp = floor(sqrt(x)); int result = 0; result = int(tmp); return result; } };
解法二：
利用二分法查找，代码如下：
class Solution { public: int mySqrt(int x) { long long left = 0; //为了防止平方过程出现溢出，使用long long long long right = x/2+1; while(left <= right) { long long mid = (left+right)/2; if (mid*mid == x) { return mid; } else if (mid*mid < x) { left = mid + 1; } else { right = mid - 1; } } return right; } };
原文：http://www.cnblogs.com/SYSU-Bango/p/7988980.html