题目描述：

Implement int sqrt(int x).

Compute and return the square root of x.

题目大意：

实现函数 int sqrt(int x).

计算并返回x的平方根（整型）

解题思路：

题目并不要求计算sqrt(x)的精确值，只需返回小于等于sqrt(x)的最大整数即可。

方法I：二分法

Python代码：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        low, high, mid = 0, x, x / 2
        while low <= high:
            if mid * mid > x:
                high = mid - 1
            else:
                low = mid + 1
            mid = (low + high) / 2
        return mid

方法II：牛顿迭代

参考博文：牛顿迭代法快速寻找平方根 （http://www.matrix67.com/blog/archives/361）

令f(t) = t2 - x，则sqrt(x)等价于求f(t)的根

初始假设答案t = x

每一次迭代，令t = t / 2 + x / (2 * t)

新的t值为当前t值对应的函数切线与x轴的交点横坐标，这就是牛顿迭代的本质

Python代码：

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        t = x
        while t * t > x:
            t = int(t / 2.0 + x / (2.0 * t))
        return t

 

本文链接：http://bookshadow.com/weblog/2015/08/29/leetcode-sqrtx/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码