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

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

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

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
}