# Implement int sqrt(int x).
#
# Compute and return the square root of x.
#
# x is guaranteed to be a non-negative integer.
#
# Example 1:
# Input: 4
# Output: 2
#
# Example 2:
# Input: 8
# Output: 2
#
# Explanation: The square root of 8 is 2.82842...,
# and since we want to return an integer, the decimal part will be truncated.
二分法查找:start = 0, end = x, mid = (start+end)/2
(1) x/mid = mid:return mid
(2) x/mid < mid:end = mid-1
(3) x/mid > mid:start = mid+1
class Solution():
def mySqrt(self, x):
if x < 2:
return x
left, right = 1, x // 2
while left <= right:
mid = left + (right - left) // 2
if mid > x // mid:
right = mid - 1
else:
left = mid + 1
return left - 1
if __name__ == "__main__":
assert Solution().mySqrt(10) == 3