# Sorted Matrix Search

# 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

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

```id="sm-2"
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

```id="py-sm"
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)
```

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