Binary Search: Square Root of x (Neetcode)

You are given a non-negative integer $$x$$ . Return the square root of $$x$$ , rounded down to the nearest integer. Do not use any built-in exponent or power functions.

Answer

The idea is to perform a binary search on the interval $$[0, x]$$ (not $$[0, x-1]$$ because we cannot go negative). For each midpoint $$m$$ , compute $$m^2$$ . If $$m^2 = x$$ , return $$m$$ . If $$m^2 < x$$ , store $$m$$ as a potential answer (since $\sqrt{13}=3$ and $$3^2 < 13$$ ), then move $$l$$ right to try larger values. This potential answer is corrected each time we enter this if. Otherwise, move $$r$$ left.

class Solution:
    def mySqrt(self, x: int) -> int:
        l, r = 0, x
        ans = 0

        while l <= r:
            m = (l + r) // 2
            sq = m*m

            if sq == x:
                return m
            
            if sq < x:
                ans = m     # possible candidate; try larger
                l = m + 1
            else:
                r = m - 1
        
        return ans

Time complexity: $O(\log x)$ .

Space complexity: $$O(1)$$ .