leetcode69 Sqrt(x)

 1 """
 2 Implement int sqrt(int x).
 3 Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
 4 Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
 5 Example 1:
 6 Input: 4
 7 Output: 2
 8 Example 2:
 9 Input: 8
10 Output: 2
11 Explanation: The square root of 8 is 2.82842..., and since
12              the decimal part is truncated, 2 is returned.
13 """
14 """
15 一道easy题被我做的一波三折
16 """
17 """
18 第一种解法 遍历找i*i <= x <(i+1)*(i+1)
19 wrong answer
20 Input: 2147395599
21 Output: 99
22 Expected: 46339
23 """
24 class Solution1:
25     def mySqrt(self, x):
26         for i in range(100):
27             if i*i <= x <(i+1)*(i+1):
28                 break
29         return i
30 """
31 第二种解法开始考虑二分，但
32 Time Limit Exceeded
33 """
34 class Solution2:
35     def mySqrt(self, x):
36         i = x // 2
37         while i*i != x:   #这里没有抓住本质的停止迭代条件
38             if i*i > x:
39                 i = i // 2
40             else:
41                 i = ((i // 2) + i) // 2
42         return i
43 """
44 正确的二分法，left, mid, right
45 """
46 class Solution3:
47     def mySqrt(self, x):
48         left = 0
49         right = x
50         while left <= right:
51             mid = (left + right) // 2
52             s = mid*mid
53             if x == s:
54                 return mid
55             elif x > s:
56                 left = mid + 1
57             else:
58                 right = mid - 1
59         return right
60 
61 """
62 高级解法：牛顿迭代法
63 传送门：https://blog.csdn.net/weixin_42130471/article/details/82730562
64 r[i] = r[i-1]/2+x/r[i-1]/2
65 """
66 class Solution4:
67     def mySqrt(self, x):
68         r = x
69         while r*r > x:
70             r = (r + x//r) // 2 #!!!牛顿迭代方程
71         return r