Valid Perfect Square: Binary Search Without sqrt()

Valid Perfect Square is LeetCode 367. Given a positive integer num, return true if it is a perfect square and false otherwise. The catch: you cannot use any built-in square root function like math.sqrt. You have to figure out whether a perfect integer root exists using only arithmetic.

The problem sounds like it needs some clever math trick, but it turns out binary search handles it cleanly. You search the range of candidate values, square each midpoint, and compare to num. Two iterations find the answer for num=16.

The approach

The key insight is that mid * mid is a monotonically increasing function over positive integers. For small values of mid the square is less than num, and for large values it is greater. There is exactly one point where it could equal num. That monotonic structure is what makes binary search applicable.

Set lo = 1 and hi = num. On each iteration, compute mid = (lo + hi) // 2 and square it:

• If mid * mid == num, you found a perfect square. Return True.
• If mid * mid > num, the midpoint is too large. Set hi = mid - 1.
• If mid * mid < num, the midpoint is too small. Set lo = mid + 1.

If the loop ends without finding an exact match, return False.

One practical note: for large num, you can start hi at num // 2 + 1 instead of num itself, since the square root of any number greater than 1 is less than half the number. This shrinks the initial search space, though the asymptotic complexity is still O(log n).

The code

def isPerfectSquare(num: int) -> bool:
    lo, hi = 1, num
    while lo <= hi:
        mid = (lo + hi) // 2
        sq = mid * mid
        if sq == num:
            return True
        elif sq < num:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

The loop runs while the search window is non-empty. Each iteration either finds the answer immediately or discards half the remaining candidates. If the pointers cross without a match, no integer root exists and the function returns False.

In Python, mid * mid never overflows because Python integers have arbitrary precision. In a statically typed language like Java or C++, squaring a large mid can overflow a 32-bit integer, so you would want to compare mid against num / mid instead, or use a 64-bit integer type.

Complexity

Each iteration halves the search space. Starting from num candidates, you need at most log2(num) iterations. For a 32-bit integer, that is at most 31 steps regardless of the input.

Building blocks

This problem belongs to the family of binary search on answer space problems. Instead of searching through a sorted array for a target value, you search through a range of candidate answers. The monotonic property of mid * mid plays the same role that sorted order plays in a standard binary search: it tells you which direction to move.

The pattern is: pick a number, check a condition based on that number, move left or right. Any time you can frame a problem as "find the number in range [lo, hi] that satisfies some monotonic condition," binary search applies directly.

Sqrt(x) uses the exact same skeleton. The only difference is that Sqrt(x) asks for the largest mid where mid * mid is at most num, while Valid Perfect Square asks whether any mid gives mid * mid equal to num. Both problems search the same candidate range and use the same comparison logic.

Edge cases

• num = 1: lo = 1, hi = 1, mid = 1. 1 * 1 = 1 equals num. Returns True. This is the smallest perfect square and the loop handles it in one step.
• Large perfect squares: For something like num = 2147395600 (the square of 46340), binary search still reaches the answer in at most 31 iterations. The exact match condition handles it the same way as small inputs.
• Non-perfect squares like num = 14: mid will take values 7, 3, 4 in successive steps. 7*7=49 > 14, 3*3=9 < 14, 4*4=16 > 14. After that lo > hi and the function returns False. No integer squares to 14.

From understanding to recall

The logic is clear: binary search the candidate values, square the midpoint, compare. But the exact form that sticks in your fingers is the tricky part. Is the loop condition lo <= hi or lo < hi? Do you return hi or False when the loop exits? What are the initial bounds?

The answer to all of these is simpler here than in most binary search variants because you have a three-way branch: equal, less than, greater than. The lo <= hi form with three explicit branches and a return False fallthrough is the most natural fit. Once you have written it a few times from scratch, those choices become obvious rather than a source of doubt.

Spaced repetition makes the difference. The key insight to lock in is "search the candidate value, square it, compare to target" rather than anything more complex. That single idea reconstructs the full solution.

Related posts

• Sqrt(x) - same binary search skeleton applied to integer square root
• First Bad Version - another binary search on a predicate over integers
• Binary Search - the foundational binary search pattern