Sorted Matrix Search

Sorted matrix search finds a target in a matrix where each row and each column is sorted. Unlike saddleback search, this approach uses divide and conquer to recursively eliminate regions.

Problem

Given a matrix $A$ of size $n \times m$ such that:

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

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

find a position $(i, j)$ such that:

$$ A[i][j] = x $$

If no such position exists, return $(-1, -1)$.

Key Idea

Select a middle column and perform binary search on that column to locate a candidate row.

This splits the matrix into regions where the target may still exist. Discard regions that cannot contain the target.

The process repeats recursively on smaller submatrices.

Algorithm

sorted_matrix_search(A, x, top, bottom, left, right):
    if top > bottom or left > right:
        return (-1, -1)

    mid_col = (left + right) // 2

    # binary search in mid column
    l = top
    r = bottom
    while l <= r:
        mid_row = (l + r) // 2
        if A[mid_row][mid_col] == x:
            return (mid_row, mid_col)
        elif A[mid_row][mid_col] < x:
            l = mid_row + 1
        else:
            r = mid_row - 1

    # search in two submatrices
    # top-right
    res = sorted_matrix_search(A, x, top, r, mid_col + 1, right)
    if res != (-1, -1):
        return res

    # bottom-left
    return sorted_matrix_search(A, x, l, bottom, left, mid_col - 1)

Wrapper:

search(A, x):
    return sorted_matrix_search(A, x, 0, n-1, 0, m-1)

Example

Let

$$ A = \begin{bmatrix} 1 & 4 & 7 & 11
2 & 5 & 8 & 12
3 & 6 & 9 & 16
10 & 13 & 14 & 17 \end{bmatrix} $$

and

$$ x = 6 $$

The algorithm narrows the search to the appropriate submatrix and eventually finds:

$$ (2, 1) $$

Correctness

Binary search in the middle column identifies a boundary row:

• All elements above are $\le A[mid]$
• All elements below are $\ge A[mid]$

If the target is not found, only two subregions can still contain it:

• upper-right region
• lower-left region

Other regions are eliminated because their values are strictly too small or too large.

Recursive calls preserve correctness by only exploring feasible regions.

Complexity

Let $n$ be rows and $m$ be columns.

cost	value
time	$O(n \log m)$ or $O(m \log n)$ depending on orientation
space	$O(\log n)$ recursion

This is typically slower than saddleback search for a single query.

Comparison

method	requirement	time
saddleback search	row and column sorted	$O(n + m)$
divide and conquer	row and column sorted	$O(n \log m)$

Saddleback search is simpler and faster in most cases.

When to Use

• When recursive decomposition fits the problem structure
• When extending to higher dimensions
• When combining with other divide-and-conquer strategies

Notes

• More complex than necessary for simple lookup
• Demonstrates matrix partitioning technique
• Can be adapted for parallel execution

Implementation

def sorted_matrix_search(a, x):
    if not a or not a[0]:
        return -1, -1

    n, m = len(a), len(a[0])

    def helper(top, bottom, left, right):
        if top > bottom or left > right:
            return -1, -1

        mid_col = (left + right) // 2

        l, r = top, bottom
        while l <= r:
            mid_row = (l + r) // 2
            if a[mid_row][mid_col] == x:
                return mid_row, mid_col
            elif a[mid_row][mid_col] < x:
                l = mid_row + 1
            else:
                r = mid_row - 1

        res = helper(top, r, mid_col + 1, right)
        if res != (-1, -1):
            return res

        return helper(l, bottom, left, mid_col - 1)

    return helper(0, n - 1, 0, m - 1)

func SortedMatrixSearch(a [][]int, x int) (int, int) {
    if len(a) == 0 || len(a[0]) == 0 {
        return -1, -1
    }

    var helper func(int, int, int, int) (int, int)

    helper = func(top, bottom, left, right int) (int, int) {
        if top > bottom || left > right {
            return -1, -1
        }

        midCol := (left + right) / 2

        l, r := top, bottom
        for l <= r {
            midRow := (l + r) / 2
            if a[midRow][midCol] == x {
                return midRow, midCol
            } else if a[midRow][midCol] < x {
                l = midRow + 1
            } else {
                r = midRow - 1
            }
        }

        if i, j := helper(top, r, midCol+1, right); i != -1 {
            return i, j
        }

        return helper(l, bottom, left, midCol-1)
    }

    return helper(0, len(a)-1, 0, len(a[0])-1)
}