69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

---

本题要对一个数开平方根。相当于LeetCode Valid Perfect Square的逆过程，很多方法都可以通用。 解法1。直接借用LeetCode Valid Perfect Square提到的牛顿法开方，代码如下：

class Solution {
public:
    int mySqrt(int x)
    {
        long long y = x;
        while (y * y > x) {
            y = (y + x / y) / 2;
        }
        return y;
    }
};

本代码提交AC，用时6MS。

解法2。二分搜索，由于sqrt(x)不可能超过x/2+1（查看两个函数图像），所以可以在[0,x/2+1]范围内二分搜索，因为是向下取整，所以返回的是r，代码如下：

class Solution {
public:
    int mySqrt(int x)
    {
        long long l = 0, r = x / 2 + 1;
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long prod = mid * mid;
            if (prod == x)
                return mid;
            if (prod < x)
                l = mid + 1;
            else
                r = mid – 1;
        }
        return r;
    }
};

本代码提交AC，用时6MS。

三刷。暴力枚举：

class Solution {
public:
	int mySqrt(int x) {
		long long xx = x;
		if (x == 1)return 1;
		long long i = 1;
		for (; i < xx; ++i) {
			if (i*i > xx)break;
		}
		return i - 1;
	}
};

本代码提交AC，用时16MS，还是用前两个方法吧。