Integer Square Root: Search the Answer Space

This one is a Easy-rated classic reported from Amazon, Bloomberg, Apple interviews: "Sqrt(x)". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Modified Binary Search pattern on sight. Part 7 of 11 in the Modified Binary Search arc.

The Problem

Given a non-negative integer x, return the integer part of its square root without using built-in power functions. Small on its own, but it introduces search-on-the-answer — the technique behind the hardest questions in this arc — in its purest form.

Input:  x = 8
Output: 2
The square root of 8 is 2.828..., truncated to 2.

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

There is no array — the search space is the answer range 0..x itself, and the predicate 'k squared is at most x' is monotonic: true, true, true, then false forever. Any monotonic predicate over integers is binary-searchable; that reframing is the entire lesson.

The Approach

Search k in [0, x]. If k squared is at most x, k is feasible — record it and go right for a bigger one; otherwise go left. This is the find-last-true boundary, the mirror of lower bound's find-first-true.

Newton's method converges faster and makes a great mention, but the interviewer is teaching-testing the boundary template here — deliver that first, cleanly.

Python Solution

def my_sqrt(x: int) -> int:
    """Largest k such that k * k <= x."""
    lo, hi = 0, x
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid                  # feasible: try bigger
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

Complexity

• Time: O(log x) — halving over the numeric range
• Space: O(1) — constant arithmetic state

Interview Tips and Follow-Ups

• The record-and-continue (ans = mid) template avoids boundary-return headaches — reuse it verbatim in Koko and Ship Capacity next.
• In fixed-width languages mid * mid overflows — compare mid <= x // mid instead. Python is immune; say so anyway.
• Escalation: pow(x, n) by fast exponentiation, and Valid Perfect Square — both live in the same answer-space family.

That wraps part 7 of the Modified Binary Search arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.