# Matrix Binary Search

# Matrix Binary Search

Matrix binary search searches a sorted matrix by treating its entries as one virtual sorted array. It applies when the matrix is sorted in row-major order.

For a matrix with $n$ rows and $m$ columns, row-major sorted means:

* each row is sorted
* the first value of each row is greater than the last value of the previous row

This condition allows the matrix to be searched with ordinary binary search.

## Problem

Given a matrix $A$ with $n$ rows and $m$ columns, and a target value $x$, find whether $x$ occurs in the matrix.

Assume:

$$
A[i][j] \le A[i][j+1]
$$

within each row, and

$$
A[i][m-1] < A[i+1][0]
$$

between consecutive rows.

## Key Idea

Map a one-dimensional index $k$ into matrix coordinates:

$$
i = \left\lfloor \frac{k}{m} \right\rfloor
$$

$$
j = k \bmod m
$$

Then binary search over the virtual range:

$$
[0, nm - 1]
$$

## Algorithm

```id="matrix-bs-1"
matrix_binary_search(A, x):
    n = number of rows
    m = number of columns

    l = 0
    r = n * m - 1

    while l <= r:
        k = l + (r - l) // 2
        i = k // m
        j = k % m

        if A[i][j] == x:
            return (i, j)
        else if A[i][j] < x:
            l = k + 1
        else:
            r = k - 1

    return (-1, -1)
```

## Example

Let

$$
A =
\begin{bmatrix}
1 & 3 & 5 \
7 & 9 & 11 \
13 & 15 & 17
\end{bmatrix}
$$

and

$$
x = 11
$$

The matrix is treated as:

$$
[1, 3, 5, 7, 9, 11, 13, 15, 17]
$$

Binary search finds virtual index $5$.

Convert back:

$$
i = 5 // 3 = 1
$$

$$
j = 5 \bmod 3 = 2
$$

Return:

$$
(1, 2)
$$

## Correctness

The row-major ordering condition makes the virtual sequence sorted. The mapping from virtual index $k$ to matrix position $(i, j)$ preserves this order.

Binary search is correct on sorted sequences. Since every matrix element appears exactly once in the virtual sequence, the returned coordinate is correct if the target exists. If the search interval becomes empty, the target does not occur.

## Complexity

Let $N = n \cdot m$.

| case      | time        |
| --------- | ----------- |
| all cases | $O(\log N)$ |

Equivalently:

$$
O(\log(nm))
$$

Space:

$$
O(1)
$$

## Comparison

| method                 | requirement      | time          |
| ---------------------- | ---------------- | ------------- |
| scan all cells         | none             | $O(nm)$       |
| binary search each row | rows sorted      | $O(n \log m)$ |
| matrix binary search   | row-major sorted | $O(\log(nm))$ |

## When to Use

Use matrix binary search when:

* the matrix is row-major sorted
* random access to cells is available
* the target is a single value lookup
* the matrix can be interpreted as one sorted array

## Notes

This method does not apply to matrices where each row and column is sorted independently but row boundaries do not form one global order. For that case, use saddleback search or sorted matrix search.

## Implementation

```id="py-matrix-bs"
def matrix_binary_search(a, x):
    if not a or not a[0]:
        return -1, -1

    n, m = len(a), len(a[0])
    l, r = 0, n * m - 1

    while l <= r:
        k = l + (r - l) // 2
        i, j = divmod(k, m)

        if a[i][j] == x:
            return i, j
        elif a[i][j] < x:
            l = k + 1
        else:
            r = k - 1

    return -1, -1
```

```id="go-matrix-bs"
func MatrixBinarySearch(a [][]int, x int) (int, int) {
    if len(a) == 0 || len(a[0]) == 0 {
        return -1, -1
    }

    n, m := len(a), len(a[0])
    l, r := 0, n*m-1

    for l <= r {
        k := l + (r-l)/2
        i := k / m
        j := k % m

        if a[i][j] == x {
            return i, j
        } else if a[i][j] < x {
            l = k + 1
        } else {
            r = k - 1
        }
    }

    return -1, -1
}
```