sqrtx

发表于 | 分类于 ， | 阅读次数 | 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
https://leetcode.com/problems/sqrtx/description/
"""


class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        >>> s = Solution()
        >>> s.mySqrt(4)
        2
        >>> s.mySqrt(0)
        0
        >>> s.mySqrt(8)
        2
        >>> s.mySqrt(1)
        1
        >>> s.mySqrt(2147395600)
        46340
        """
        if 0 <= x < 1:
            return 0
        elif x == 1:
            return 1
        else:
            # how to choose the init value ?
            x0 = x // 2
            while True:
                # x**2/4 > x
                if x0**2 <= x:
                    return x0
                x0 = int((x0 + x / x0) / 2)