Square Root (Integer)

Square Root (Integer) asks for the whole-number part of a square root without ever calling sqrt. It is a clean, classic use of binary search on the answer — the search space is not an array you are given, but the range of possible answers itself.

The slow way first

The obvious idea: count up from 0, squaring each candidate, until the square passes x, then back off by one. For x = 50 you would test 0, 1, 2, ... , 7, 8 and stop. That works, but it is O(sqrt(x)) — for very large x (think billions) you would loop tens of thousands of times.

The question to ask: is the candidate range sorted? It is. If m * m <= x, then every smaller value also squares to something <= x; if m * m > x, every larger value is too big as well. That monotonic split is exactly what binary search needs.

The idea: binary-search the answer

The answer lives somewhere in [0, x]. Keep a window [lo, hi] and repeatedly test its middle:

• Compute mid = (lo + hi) // 2.
• If mid * mid <= x, then mid is a valid root — record it as the best answer so far, and look for something even bigger by moving lo = mid + 1.
• Otherwise mid is too big, so throw away the upper half: hi = mid - 1.

Each test halves the window, so we finish in O(log x) instead of O(sqrt(x)).

The trick is the record-and-keep-going move: when a candidate fits, we do not stop — we save it and push lo higher, because there might be an even larger root that also fits. The last value we record is the floor.

Walk through it

Step through the animation for x = 50. The strip shows candidate roots 0..10; the lo, mid, and hi pointers bracket the live window and ans tracks the best root found. We test mid = 25 (too big), then 12 (too big), then 5 (fits, ans = 5), then 8 (too big), then 6 (fits, ans = 6), then 7 (fits, ans = 7). Finally lo passes hi, the loop ends, and we return 7.

Pseudocode

lo, hi = 0, x          # the answer is somewhere in [0, x]
ans = 0
while lo <= hi:
    mid = (lo + hi) // 2
    if mid * mid <= x:        # mid is a valid root
        ans = mid             # remember it as the best so far
        lo = mid + 1          # try for something bigger
    else:
        hi = mid - 1          # mid too big, shrink the upper end
return ans                    # the largest valid root we saw

The Python solution

def my_sqrt(x):
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

• lo, hi, ans = 0, x, 0 opens the window on the full range and seeds the best answer at 0.
• while lo <= hi keeps going as long as the window is non-empty.
• mid = (lo + hi) // 2 is integer division, so mid is always a whole candidate root.
• Line 5 is the decision: mid * mid <= x asks whether mid is a valid root (no sqrt, just one multiply).
• Lines 6-7 are the record-and-go-right case — save mid, then push lo up to hunt for a larger root.
• hi = mid - 1 is the go-left case, dropping the half that is provably too big.
• We return ans, the largest root we ever recorded — the floor of the true square root.

Complexity

We use only a handful of integer variables, so the extra space is O(1). Halving the candidate range each step turns an O(sqrt(x)) scan into an O(log x) search — for x near a billion, that is roughly 30 iterations instead of 30,000.

When this pattern shows up

Practice