# Saddleback Search

# Saddleback Search

Saddleback search finds a target in a matrix where each row and each column is sorted in nondecreasing order. It walks through the matrix along a monotone path, eliminating one row or one column at each step.

## Problem

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

$$
A[i][j] \le A[i][j+1] \quad \text{(rows sorted)}
$$

$$
A[i][j] \le A[i+1][j] \quad \text{(columns sorted)}
$$

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

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

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

## Key Idea

Start from the **top-right corner**:

* At $(0, m-1)$

At each step:

* If current value equals $x$, return it
* If current value is greater than $x$, move left
* If current value is less than $x$, move down

Each move discards one row or one column.

## Algorithm

```id="saddle-1"
saddleback_search(A, x):
    n = number of rows
    m = number of columns

    i = 0
    j = m - 1

    while i < n and j >= 0:
        if A[i][j] == x:
            return (i, j)
        else if A[i][j] > x:
            j = j - 1
        else:
            i = i + 1

    return (-1, -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 = 9
$$

Path:

| step | position | value | action    |
| ---- | -------- | ----- | --------- |
| 1    | (0, 3)   | 11    | move left |
| 2    | (0, 2)   | 7     | move down |
| 3    | (1, 2)   | 8     | move down |
| 4    | (2, 2)   | 9     | found     |

Return $(2, 2)$.

## Correctness

At each step, the algorithm maintains a candidate region where the target may lie.

From the top-right corner:

* All elements below are larger
* All elements to the left are smaller

If $A[i][j] > x$, then every element below in column $j$ is greater than or equal to $A[i][j]$, so none can equal $x$. The column can be discarded.

If $A[i][j] < x$, then every element to the left in row $i$ is less than or equal to $A[i][j]$, so none can equal $x$. The row can be discarded.

Each step reduces the search space while preserving all possible positions of $x$.

## Complexity

| dimension | cost       |
| --------- | ---------- |
| rows      | $n$        |
| columns   | $m$        |
| total     | $O(n + m)$ |

Space:

$$
O(1)
$$

## Comparison

| method                | requirement             | time          |
| --------------------- | ----------------------- | ------------- |
| full scan             | none                    | $O(nm)$       |
| binary search per row | rows sorted             | $O(n \log m)$ |
| saddleback search     | rows and columns sorted | $O(n + m)$    |

## Variants

| start point | direction         |
| ----------- | ----------------- |
| top-right   | move left or down |
| bottom-left | move up or right  |

Both give the same complexity.

## When to Use

* Matrix sorted by rows and columns
* Efficient elimination of rows or columns
* Large matrices where $n + m \ll nm$

## Notes

* Does not require global ordering across rows
* Works with duplicates
* Deterministic path with no backtracking

## Implementation

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

    n, m = len(a), len(a[0])
    i, j = 0, m - 1

    while i < n and j >= 0:
        if a[i][j] == x:
            return i, j
        elif a[i][j] > x:
            j -= 1
        else:
            i += 1

    return -1, -1
```

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

    n, m := len(a), len(a[0])
    i, j := 0, m-1

    for i < n && j >= 0 {
        if a[i][j] == x {
            return i, j
        } else if a[i][j] > x {
            j--
        } else {
            i++
        }
    }

    return -1, -1
}
```