Leetcode: Square Root (Sqrt)

Sqrt(x) | LeetCode OJ

Square root of n will lie in the range [1, n]. So we need to search for x in a sorted array such that x*x equals given number. As you can see its a simple application of binary search

Refer to the blog post on binary search to understand how the algorithm and the code works

Time and space complexity are O(log n) and O(1) respectively

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        low, high = 0, x + 1
        mid = (low + high) / 2
        while mid != low:
            val = mid * mid
            if val == x:
                return mid
            if val < x:
                low = mid
            else:
                high = mid
            mid = (low + high) / 2
        return low