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
}