141. Sqrt(x)【牛顿迭代法求平方根 by java】

Description

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

题意：求给定数的平方根，如果用一般的方法，例如二分法之类的，需要考虑一下int型的范围，别溢出。最好的方法时牛顿迭代法。代码如下：

public class Solution {

    /**

     * @param x: An integer

     * @return: The sqrt of x

     */

    public int sqrt(int x) {

        // write your code here

       //牛顿迭代法求平方根

       double p=2.0;

       double pre=0;

       while(Math.abs(p-pre)>1e-6){

           pre=p;

           p=(p+x/p)/2.0;

       }

       return (int)p;

    }

}

关于牛顿迭代法在平方根上的应用原理，参阅博客： http://www.matrix67.com/blog/archives/361