# Integer Square Root by Binary Search

# 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

```text id="isqrt-1"
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:

```text id="isqrt-overflow-bad"
m * m <= n
```

may overflow.

Use division instead:

```text id="isqrt-overflow-good"
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:

```text id="isqrt-bound"
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

```python id="py-isqrt"
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
```

```go id="go-isqrt"
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
}
```