# Array Bounds Checking

# Array Bounds Checking

Array bounds checking verifies that an index lies inside the valid range before reading or writing an array element. It prevents invalid memory access and makes failures explicit.

You use it whenever array access may receive an index from input, another computation, or an unsafe source.

## Problem

Given an array $A$ of length $n$ and an index $i$, determine whether:

$$
0 \le i < n
$$

If the condition holds, the access is valid. Otherwise, the access must fail safely.

## Algorithm

Check the index before reading:

```id="array-bounds-get"
get(A, i):
    if i < 0 or i >= length(A):
        error "index out of bounds"

    return A[i]
```

Check the index before writing:

```id="array-bounds-set"
set(A, i, x):
    if i < 0 or i >= length(A):
        error "index out of bounds"

    A[i] = x
```

## Example

Let

$$
A = [8, 3, 5, 1, 9]
$$

Then:

| index | condition      | result  |
| ----: | -------------- | ------- |
|     2 | $0 \le 2 < 5$  | valid   |
|     5 | $0 \le 5 < 5$  | invalid |
|    -1 | $0 \le -1 < 5$ | invalid |

Reading index $2$ returns:

$$
5
$$

Reading index $5$ fails because the last valid index is $4$.

## Correctness

The valid indices of an array of length $n$ are exactly $0$ through $n - 1$. The condition $0 \le i < n$ accepts every valid index and rejects every invalid index. Therefore, any access that passes the check refers to an existing element, and any access that fails the check is prevented.

## Complexity

| operation    |   time |
| ------------ | -----: |
| bounds check | $O(1)$ |
| checked get  | $O(1)$ |
| checked set  | $O(1)$ |

Space usage:

$$
O(1)
$$

## When to Use

Bounds checking is appropriate when:

* indices come from user input
* indices come from arithmetic
* correctness and safety matter
* invalid access should produce a clear error

It is less suitable only in carefully audited low-level code where bounds are already proven and performance requires removing redundant checks.

## Implementation

```python id="array-bounds-python"
def get(a, i):
    if i < 0 or i >= len(a):
        raise IndexError("index out of bounds")
    return a[i]

def set_value(a, i, x):
    if i < 0 or i >= len(a):
        raise IndexError("index out of bounds")
    a[i] = x
```

```go id="array-bounds-go"
func Get[T any](a []T, i int) (T, bool) {
    var zero T
    if i < 0 || i >= len(a) {
        return zero, false
    }
    return a[i], true
}

func Set[T any](a []T, i int, x T) bool {
    if i < 0 || i >= len(a) {
        return false
    }
    a[i] = x
    return true
}
```