Integer Square Root by Binary Search

Integer square root by binary search computes the largest integer $r$ such that:

$$ r^2 \le n $$

For a nonnegative integer $n$, this value is written as:

$$ \lfloor \sqrt{n} \rfloor $$

The algorithm avoids floating point arithmetic and gives an exact integer result.

Problem

Given a nonnegative integer $n$, find the largest integer $r$ such that:

$$ r^2 \le n $$

Equivalently:

$$ r = \lfloor \sqrt{n} \rfloor $$

Key Idea

The predicate:

$$ m^2 \le n $$

is monotone over nonnegative integers.

It has the form:

$$ true, true, true, false, false, false $$

So we can binary search for the last true value.

Algorithm

integer_square_root(n):
    l = 0
    r = n
    ans = 0

    while l <= r:
        m = l + (r - l) // 2

        if m * m <= n:
            ans = m
            l = m + 1
        else:
            r = m - 1

    return ans

Example

Let:

$$ n = 27 $$

We need the largest $r$ such that:

$$ r^2 \le 27 $$

Check nearby values:

r	r^2	valid
4	16	yes
5	25	yes
6	36	no

Therefore:

$$ \lfloor \sqrt{27} \rfloor = 5 $$

Correctness

The algorithm maintains ans as the largest valid value found so far.

If $m^2 \le n$, then $m$ is a valid candidate, and any larger valid answer must lie to the right. The algorithm records ans = m and moves the left boundary to m + 1.

If $m^2 > n$, then $m$ and every larger value are invalid, so the algorithm moves the right boundary to m - 1.

When the search ends, all candidates have been classified. The stored ans is the largest integer whose square is at most $n$.

Complexity

cost	value
iterations	$O(\log n)$
time	$O(\log n)$
space	$O(1)$

Overflow Avoidance

In fixed-width integer languages, the expression:

m * m <= n

may overflow.

Use division instead:

m <= n // m

when $m > 0$.

This tests the same condition without multiplying two possibly large integers.

Optimized Bound

For $n \ge 2$, the square root is at most:

$$ \frac{n}{2} $$

So the initial range may be reduced to:

l = 1
r = n // 2

For simplicity, many implementations use $[0, n]$.

When to Use

Use integer square root when:

• exact integer arithmetic is required
• floating point rounding is unacceptable
• the input may be large
• you need a safe floor square root

Common uses include number theory, primality testing, integer geometry, and binary search exercises.

Implementation

def integer_square_root(n):
    if n < 0:
        raise ValueError("n must be nonnegative")

    l, r = 0, n
    ans = 0

    while l <= r:
        m = l + (r - l) // 2

        if m == 0 or m <= n // m:
            ans = m
            l = m + 1
        else:
            r = m - 1

    return ans

func IntegerSquareRoot(n int) int {
    if n < 0 {
        return -1
    }

    l, r := 0, n
    ans := 0

    for l <= r {
        m := l + (r-l)/2

        if m == 0 || m <= n/m {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }

    return ans
}