Sqrt(x)

Question

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

LeetCodeleetcode.com/problems/sqrtx

Solution

/*
牛顿迭代法：x^2 = a
某一点x0的切线方程为 f(x) - f(x0) = f'(x0) (x-x0);
=> x = (x0 + a/x0) / 2;
*/
public int mySqrt(int x) {
    double x0 = x;
    double x1 = (x0 + x/x0) / 2.0;
    
    double accuracy = 1e-6;
    while (Math.abs(x0-x1) >= accuracy) {
        x0 = x1;
        x1 = (x0 + x/x0) / 2.0;
    }
    return (int) x1;
}