leetCode: Sqrt(x)

1. 题目： 求解平方根

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.

2. 方法一： 二分法

    public static int mySqrt(int x) {
        if (1 >= x)
            return x;
        int low = 1;
        int high = x;
        while (low < high) {
            int mid = low + (high - low + 1) / 2;
            if (mid <= x / mid) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

3. 方法二： 牛顿迭代法

public static int newtonSqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x/r) / 2;
        }
        return (int) r;
    }

作者 @没有故事的老大爷
为什么总在，那些飘雨的日子， 深深的把你想起。