/// 解法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;

    }

};