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

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

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

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
}