Environment: Python 3.7
Key technique: Binary Search, //
int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
Use binary search to find ans. If input is 1, just return answer 1. The brief process is as below.
def mySqrt(self, num):
left = 0
right = num
while(left <= right):
mid = (left + right)//2
if(mid**2 < num):
left = mid + 1
elif(mid**2 > num):
right = mid -1
return left -1