Module 12 · Binary Search and Monotone Answer Spaces

115. Integer Square Root

Bridge · Download this solution · All solutions and shared helpers

Problem

For a nonnegative integer n, return floor(sqrt(n)) without using square-root functions. The result r must satisfy r*r<=n<(r+1)*(r+1). Zero is allowed.

Examples

Example 1

integer_sqrt(17)
=> 4

Four squared fits; five squared exceeds seventeen.

Example 2

integer_sqrt(0)
=> 0

The first excluded square belongs to one.

Example 3

integer_sqrt(16)
=> 4

Perfect squares retain their exact integer root.

Reveal the worked solution and reasoning

Why this mechanism works

Search for the first integer whose square exceeds n, then subtract one. Squares are monotone over nonnegative integers, creating a false-then-true predicate. The search boundary n+1 is sufficient even for the small cases zero and one, where it may serve as the first excluded sentinel.

State and boundaries

left and right bound the first integer x with x*x>n. All smaller confirmed candidates satisfy x*x<=n.

Protocol

Search integers with left=0,right=n+1.
On mid*mid>n set right=mid.
Otherwise set left=mid+1.
Return left-1.

Visualization

n=17
x:       0 1 2 3 4 5 ...
x*x>17: F F F F F T ...
first True 5 -> floor root 4

Python implementation

def integer_sqrt(n):
    left, right = 0, n + 1
    while left < right:
        mid = (left + right) // 2
        if mid * mid > n:
            right = mid
        else:
            left = mid + 1
    return left - 1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

integer_sqrt(17)

L2 integer_sqrt: left, right = 0, n + 1
n=17; left=0; right=18

L4 integer_sqrt: mid = (left + right) // 2
n=17; left=0; right=18; mid=9

L6 integer_sqrt: right = mid
n=17; left=0; right=9; mid=9

L4 integer_sqrt: mid = (left + right) // 2
n=17; left=0; right=9; mid=4

L8 integer_sqrt: left = mid + 1
n=17; left=5; right=9; mid=4

L4 integer_sqrt: mid = (left + right) // 2
n=17; left=5; right=9; mid=7

L6 integer_sqrt: right = mid
n=17; left=5; right=7; mid=7

L4 integer_sqrt: mid = (left + right) // 2
n=17; left=5; right=7; mid=6

L6 integer_sqrt: right = mid
n=17; left=5; right=6; mid=6

L4 integer_sqrt: mid = (left + right) // 2
n=17; left=5; right=6; mid=5

L6 integer_sqrt: right = mid
n=17; left=5; right=5; mid=5

Result: 4. Four squared fits; five squared exceeds seventeen.

integer_sqrt(0)

L2 integer_sqrt: left, right = 0, n + 1
n=0; left=0; right=1

L4 integer_sqrt: mid = (left + right) // 2
n=0; left=0; right=1; mid=0

L8 integer_sqrt: left = mid + 1
n=0; left=1; right=1; mid=0

Result: 0. The first excluded square belongs to one.

Why the solution is correct

Monotonic squares allow the standard first-true boundary proof. At convergence left is the first integer with square too large, including a sentinel beyond the tested range in the smallest cases. Its predecessor is therefore the largest integer with square at most n.

Time and space

O(log(n+1)) integer comparisons and multiplications; O(1) integer variables. Big-integer multiplication has bit-length-dependent cost.

Common mistakes

Searching for exact square equality fails for nonsquares. Floating-point square roots can round near large perfect squares.

Reasoning card

State: left and right bound the first integer x with x*x>n. All smaller confirmed candidates satisfy x*x<=n.

Invariant: Feasible and infeasible regions remain separated.

Decision to rehearse: Binary-search feasible values x where x*x <= n.

Finish: Return left-1

Transfer exercise

In a fixed-width language, replace mid*mid with a division-based comparison while guarding the zero case.