# leetcode 69. Sqrt(x)（python）

2022-01-29 19:23:12

Little knowledge , Great challenge ！ This article is participating in “ A programmer must have a little knowledge ” Creative activities .

### describe

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

``````Input: x = 4
Output: 2
Copy code ``````

Example 2:

``````Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
Copy code ``````

Note:

``````0 <= x <= 2^31 - 1
Copy code ``````

### analysis

Give a number in the title x , Ask to find out the square result of it , If it is an integer, the result will be returned directly , If it is a decimal result, only the integer part is returned , The idea is simple （ It's careless , Submitted several times and burst ERROR 了 , It's really a shame ）：

• Direct traversal [0, x // 2 + 2] Every integer in the range i
• If i * i == x , Go straight back to i
• If i * i > x , Go straight back to i-1

Even more humiliating is , The solution finally timed out , Read the requirements in the title , x The magnitude of is really too big ...

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
for i in range(0, x // 2 + 2):
if i * i == x:
return i
if i * i > x:
return i - 1

Copy code ``````

### Running results

``````Memory Limit Exceeded
Copy code ``````

### analysis

Of course, you can directly use the binary search method to find .

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
l, r = 0, x
while l <= r:
mid = (l + r) // 2
if mid ** 2 <= x < (mid + 1) ** 2:
return mid
elif x < mid ** 2:
r = mid - 1
else:
l = mid + 1
Copy code ``````

### Running results

``````Runtime: 37 ms, faster than 37.53% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
Copy code ``````

### analysis

Of course, using built-in functions can also , But more opportunistic .

``````class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
return int(sqrt(x))
Copy code ``````

### Running results

``````Runtime: 25 ms, faster than 61.40% of Python online submissions for Sqrt(x).
Memory Usage: 13.3 MB, less than 66.04% of Python online submissions for Sqrt(x).
Copy code ``````