/// 解法1: O(sqrt(n))
class Solution {
public:
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    int sqrt(int x) {
        // write your code here
        for (int i=0; i*i<=x; ++i) {
            long long temp = (long long)(i+1)*(i+1);
            if (temp > x) {
                return i;
            }
        }
    }
};

///解法2: O(log(n))

class Solution {
public:
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    int sqrt(int x) {
        // write your code her
        int l = 1;
        int r = x / 2 + 1; //  ans >= 1 && ans <= x/2 + 1
        while(l <= r) {
            long long mid = (l + r) / 2;
            long long t1 = mid * mid;
            long long t2 = (mid + 1) * (mid + 1);
            if (t1 == x || (t1 < x && t2 > x)) return mid;
            if (t1 < x) {
                l = mid + 1;
            }else r = mid - 1;
        }
    }
};

///解法3: 牛顿迭代法
/* f(x) = n - x * x
 * Xi+1 = Xi - f(Xi)/f‘(Xi)
 * Xi+1 = Xi - (n - Xi*Xi)/(-2*Xi)
 * Xi+1 = (Xi + n / Xi) / 2
 */

class Solution {
public:
    /**
     * @param x: An integer
     * @return: The sqrt of x
     */
    int sqrt(int x) {
         write your code her
        if (x == 0) return 0;
        double l = 0;
        double r = 1;
        while(l != r) {
            double t = r;
            l = (r + x*1.0 / r) / 2.0;
            r = l;
            l = t;
        }
        return (int) l;
    }
};