Leetcode 69: Sqrt(x)

Computing the integer square root of a number using Binary Search.

The original problem is here.

Binary Search Approach

• A naive Linear Search approach would involve squaring numbers starting from 1 until $i^2 > x$, then returning $i - 1$. This takes $O(\sqrt{x})$ time, which is slow for large values of $x$.
• Since the sequence of squares $(1^2, 2^2, 3^2, \dots)$ is monotonically increasing (which is equivalent to being sorted), we can optimize this to $O(\log x)$ by substituting the Linear Search for a Binary Search.

Algorithm

Instead of an array, our search space is the range of possible integer answers from $1$ up to $x$.

• Pointers Initialization: Set left = 1 and right = x.
• Midpoint calculation: At each step, compute mid = left + (right - left) // 2.
• Comparison: We compare mid * mid with x:
  • If mid * mid == x, we’ve found the exact integer root! Return mid.
  • If mid * mid > x, mid is too large to be the square root. We tighten the upper bound: right = mid - 1.
  • If mid * mid < x, the square root could be mid or something larger. We tighten the lower bound: left = mid + 1. It’s okay to discard mid even if it’s the answer. The reason is written at termination.

    Termination

• If the algorithm do not terminate by returning mid, the loop stops when the pointers cross (left > right).
• In this case, the final step is always one element right next to the answer, and mid=left=right.
• If we are left of the answer, left will be increased and the algorithm terminates. right is the answer.
• If we are right of the answer, right will be decreased by one and the algorithm terminates. right is the answer.

My solution

class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x
        while left <= right:
            mid = (left+right)//2
            mid_sq = mid*mid
            if mid_sq == x:
                return mid
            if mid_sq > x:
                right = mid - 1
            if mid_sq < x:
                left = mid+1
        return right

Complexity Analysis

• Space Complexity: $O(1)$. We only use a few integer variables (left, right, and mid) indicating indices.
• Time Complexity: $O(\log x)$. We consistently halve the active search space starting from a size of $x$, taking logarithmic operations.