69. Sqrt(x)

题目：

Implement int sqrt(int x).

Compute and return the square root of x.

题解：

求平方根。

二分法， Time Complexity - O(logn)， Space Complexity - O(1)

public class Solution {
    public int mySqrt(int x) {
        if(x <= 1)
            return x;
        int lo = 0, hi = x;
        
        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if(mid < x / mid)
                lo = mid + 1;
            else if (mid > x / mid)
                hi = mid - 1;
            else
                return mid;
        }
        
        return hi;
    }
}

牛顿法

public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;
        double lastY = 0;
        double y = 1;
        
        while (y != lastY) {
            lastY = y;
            y = (y + x / y) / 2;
        }
        
        return (int)(y);
    }
}

Bit Manipulation

public class Solution {
    public int mySqrt(int x) {
        long ans = 0;
        long bit = 1l << 16;
        
        while(bit > 0) {
            ans |= bit;
            if (ans * ans > x) {
                ans ^= bit;
            }
            bit >>= 1;
        }
        
        return (int)ans;
    }
}

Follow up - 求实数的平方根。设置一个ε，然后根据差值计算

二刷：

可以用二分法或者牛顿法。

Java:

二分法：

二分法写得比较古怪，有点像背出来的，为了避免Integer.MAX_VALUE用了 x / mid。mid不会为0，所以可以放心大胆使用。最后返回结果时要返回的是hi，这是 lo ^2会正好比x大。

Time Complexity - O(logn)， Space Complexity - O(1)

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        } 
        int lo = 0, hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid == x / mid) {
                return mid;
            } else if (mid < x / mid) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return hi;
    }
}

牛顿法：

牛顿法也可以用来处理double的情况，只要把条件改为y - lastY > epsilon就可以了。一开始设x² = a，则转化为方程y = x² - a，接下来右x_n+1 = x_n - f(x) / f'(x)。新的y (切线逼近)等于 x_n+1 = x_n - ( x²- a ) / (y的导数 = 2x)，所以简化一下就等于x_n+1 = (x_n + a / x_n) / 2，用切线进行不断逼近。

Time Complexity - O(logn)， Space Complexity - O(1)

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        } 
        double lastY = x / 2;
        double y = (lastY + x / lastY) / 2;
        while (y - lastY != 0) {
            lastY = y;
            y = (lastY + x / lastY) / 2;
        }
        return (int)y;
    }
}

三刷:

Java:

二分法：

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) return x;
        int lo = 0, hi = x;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (mid == x / mid) return mid;
            else if (mid < x / mid) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }
}

牛顿法:

再次详述一下牛顿法。

牛顿法主要是使用切线来不断逼近方程根的方法。

首先我们有x² = a，移动一下我们得到方程x² - a = 0。
我们假设函数 f(x) = x² - a, 则这个方程的切线 f'(x) = 2x，也就是切线的斜率为2
利用直线的两点式方程我们可以得到 x_n+1 - x_n= ( 0 - f(x_n) ) / f'(x_n)，这里新的逼近点为(x_n+1 ， 0)，即切线与x轴的焦点，旧的逼近点为(x_n, f(x_n))。
这里我们做一下变量代换， f'(x) = 2x， f(x) = x² - a
我们可以得到 x_n+1 - x_n= (a - x_n²) / 2 * x_n，简化一下就变成了 x_{n+1 =}(x_n + a / x_n) / 2
在 x_n+1 - x_n的差大于一个误差常数Epsilon的时候，我们就可以用while循环来不断使用切线迭代逼近方程x² - a = 0的根，最后就可以成功求得一个在Epsilon误差内的，方程的解。

public class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        } 
        double lastY = 1;
        double y = (lastY + x / lastY) / 2;
        while (y - lastY != 0) {
            lastY = y;
            y = (lastY + x / lastY) / 2;
        }
        return (int)y;
    }
}

4/4/2016：从wentao处又学习了很多东西。他是数学PHD大牛，推理和论证功力简直一级棒。

Reference：

http://www.matrix67.com/blog/archives/361

https://en.wiki2.org/wiki/Methods_of_computing_square_roots

http://www.math.harvard.edu/library/sternberg/slides/lec1.pdf

http://www.cnblogs.com/bigrabbit/archive/2012/09/25/2702174.html