Introduction

An "ordered matrix" can mean two different things, and the best search algorithm depends on which guarantee you actually have. If you choose the algorithm that matches the matrix structure, you can cut the search from linear time down to either O(m + n) or O(log(mn)).

First, Identify the Matrix Invariant

There are two common interpretations:

1. Every row is sorted and every column is sorted.
2. Every row is sorted, and the first element of each row is greater than the last element of the previous row.

These look similar, but they lead to different optimal strategies.

For example, this matrix is row-sorted and column-sorted:

110 20 30 40
215 25 35 45
327 29 37 48
432 33 39 50

This matrix is globally sorted when read row by row:

1  3  5
7  9 11
13 15 17

The second kind can be treated like a flattened sorted array. The first kind cannot.

Use Staircase Search for Row-and-Column Sorted Matrices

When each row and each column is sorted, the classic approach is to start in the top-right corner.

Why top-right? Because one comparison eliminates either:

• the current column, if the value is too large
• the current row, if the value is too small

1def search_matrix(matrix, target):
2    if not matrix or not matrix[0]:
3        return False
4
5    rows = len(matrix)
6    cols = len(matrix[0])
7    r = 0
8    c = cols - 1
9
10    while r < rows and c >= 0:
11        value = matrix[r][c]
12        if value == target:
13            return True
14        if value > target:
15            c -= 1
16        else:
17            r += 1
18
19    return False
20
21
22matrix = [
23    [10, 20, 30, 40],
24    [15, 25, 35, 45],
25    [27, 29, 37, 48],
26    [32, 33, 39, 50],
27]
28
29print(search_matrix(matrix, 29))
30print(search_matrix(matrix, 34))

This runs in O(m + n) time because each step moves either one row down or one column left.

Use Binary Search for Globally Sorted Matrices

If every row starts after the previous row ends, the whole matrix behaves like a sorted one-dimensional array. Then binary search is the best choice.

1def search_flattened(matrix, target):
2    if not matrix or not matrix[0]:
3        return False
4
5    rows = len(matrix)
6    cols = len(matrix[0])
7    left = 0
8    right = rows * cols - 1
9
10    while left <= right:
11        mid = (left + right) // 2
12        r = mid // cols
13        c = mid % cols
14        value = matrix[r][c]
15
16        if value == target:
17            return True
18        if value < target:
19            left = mid + 1
20        else:
21            right = mid - 1
22
23    return False
24
25
26matrix = [
27    [1, 3, 5],
28    [7, 9, 11],
29    [13, 15, 17],
30]
31
32print(search_flattened(matrix, 11))
33print(search_flattened(matrix, 6))

This runs in O(log(mn)) time, which is better than staircase search, but only when the matrix truly has that stronger ordering guarantee.

Why the Naive Approaches Miss the Point

A full scan is always correct, but it wastes the ordering information and costs O(mn). Searching each row separately with binary search is better at O(m log n), but it is still not optimal for either major matrix variant:

• for row-and-column sorted matrices, staircase search is better
• for globally sorted matrices, one binary search over the flattened range is better

So the efficient answer is not just "use binary search." It is "use the binary search that matches the actual invariant."

Choosing the Right Algorithm Quickly

Ask one question:

Can the matrix be viewed as a single sorted list when read row by row?

If yes, use flattened binary search. If no, but rows and columns are individually sorted, use staircase search.

That one check prevents a lot of wrong implementations. Many bugs come from assuming the stronger invariant without verifying it.

Common Pitfalls

• Using flattened binary search on a matrix that is only row-sorted and column-sorted.
• Forgetting to handle empty matrices or empty rows.
• Starting staircase search from the wrong corner. Top-left and bottom-right do not eliminate enough possibilities.
• Searching every row with binary search even when a better matrix-specific algorithm exists.
• Confusing "sorted rows" with "globally sorted across rows." They are not the same promise.

Summary

• The best search algorithm depends on the exact ordering rule of the matrix.
• Use staircase search in O(m + n) when rows and columns are both sorted.
• Use flattened binary search in O(log(mn)) when rows form one global sorted order.
• A full scan is correct but wastes the structure of the data.
• Clarifying the matrix invariant is the most important step in solving the problem efficiently.