Sqrt(x)

Question

Implement int sqrt(int x).

Compute and return the square root of x.

Tags

• Mathematics
• Binary Search

Thought

There are two ways to solve this problem:

1. Newton's method
2. Binary Search

Newton's method is of course a good algorithm, but it might be forgotten by the people during the interview. Thus, a easier algorithm should be binary search considering that we only need to find the integer which is close to the square root of the given value. The implementation detail is below.

Code

class Solution(object):
    def mySqrt(self, x):
        """
        Use binary search here
        :type x: int
        :rtype: int
        """
        low, high = 0, x
        while low <= high:
            mid = (low + high) / 2
            if mid**2 == x:
                return mid
            elif mid**2 > x:
                high = mid - 1
            else:
                low = mid + 1
        return high