Implement int sqrt(int x).

Compute and return the square root of x.

思路

利用二分法进行搜索，搜索到的结果进行平方，由此进行比对。

如果需要利用牛顿迭代法解决，最后得到的结果精度都比较高，一般来说是浮点类型的。在这题中，利用二分法可以达到预期的效果。利用牛顿迭代法反而会开销稍大。

在写二分法的时候，千万要注意边界条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x <= 1:
            return x
        else:
            origin = x
            high = x
            low = 0
            prev = x
            while (prev != (high + low) / 2):
                x = (high + low) / 2
                if x * x <= origin:
                    low = x
                else:
                    # 注意边界条件
                    high = x + 1
                prev = x
            return low

牛顿迭代法可以参考：https://en.wikipedia.org/wiki/Methods_of_computing_square_roots