Search a 2D Matrix

A matrix can be two-dimensional storage with a one-dimensional search space. Prove that shape first, then run ordinary binary search over virtual indices.

The common mistake is to see nested lists and immediately write nested loops. That works functionally, but it ignores the strongest clue in the problem: the rows are ordered relative to one another. The real question is whether reading the matrix row by row produces one globally sorted sequence.

For this problem, it does. Search virtual indices from 0 through m * n - 1, convert each midpoint into a matrix coordinate, and inspect the corresponding value. You get O(log(mn)) time and O(1) extra space without copying the matrix.

Read the contract and identify the ordering signal

Let:

• m be the number of rows.
• n be the number of columns.
• target be the integer to find.

The matrix guarantees two conditions:

1. Each row is sorted in non-decreasing order.
2. The first value of each row is greater than the last value of the previous row.

The second condition is the structural hinge. Suppose row i ends with matrix[i][n - 1], and row i + 1 begins with matrix[i + 1][0]. The contract says:

matrix[i][n - 1] < matrix[i + 1][0]

Every value in row i is at most its final value. Every value in row i + 1 is at least its first value. Therefore, every value in row i comes before every value in row i + 1 in sorted order.

Apply that argument to every adjacent pair of rows. Row-major traversal is globally non-decreasing:

matrix[0][0], matrix[0][1], ..., matrix[0][n - 1],
matrix[1][0], matrix[1][1], ..., matrix[1][n - 1],
...

That is the recognition cue:

Binary search comes from global row-major ordering, not from the fact that the input happens to be a matrix.

This distinction matters. A different matrix problem may guarantee that rows and columns are individually sorted without guaranteeing that the end of one row comes before the beginning of the next. That structure does not justify this exact flattened binary search. Use only the ordering the contract actually gives you.

Start with the baseline, then choose one search

The direct baseline scans every cell:

for row in matrix:
    for value in row:
        if value == target:
            return True
return False

It uses O(1) extra space, but it may inspect all m * n cells. Its time complexity is O(mn), which fails the explicit logarithmic requirement.

A valid improvement is to perform two binary searches:

1. Find the row whose value range could contain target.
2. Binary-search inside that row.

That takes O(log m + log n) time. Since:

log m + log n = log(mn)

it satisfies the asymptotic requirement.

However, one binary search is cleaner here. The entire matrix already behaves like one sorted sequence, so there is no reason to maintain a separate row-search state and cell-search state. Treat the matrix as a virtual one-dimensional array, while leaving the actual data untouched.

Do not flatten it with something like:

values = [value for row in matrix for value in row]

That copy costs O(mn) extra space and performs work the algorithm does not need. The matrix is already stored. We only need a way to translate a virtual index into coordinates.

Derive the virtual index mapping

Assume a matrix with m rows and n columns. Give its row-major cells virtual indices from:

0 through m * n - 1

For a 3 x 4 matrix, the layout is:

             column
             0   1   2   3
row 0        0   1   2   3
row 1        4   5   6   7
row 2        8   9  10  11

The index blocks are determined by the number of columns. Every group of n virtual indices belongs to one row.

For virtual index k:

row = k // n
column = k % n

Why?

• k // n counts how many complete rows appear before index k.
• k % n gives the position within the current row.

For example, with n = 4 and k = 9:

row    = 9 // 4 = 2
column = 9 % 4  = 1

So virtual index 9 maps to matrix[2][1].

The lookup is therefore:

matrix[k // n][k % n]

This is a flattened matrix search without allocating a flattened matrix. The virtual sequence gives binary search the one-dimensional ordering it needs; integer division and modulo reconstruct the original coordinates on demand.

The divisor is the number of columns. A row contains n values, so every n virtual positions begin a new row.

Maintain the shrinking candidate interval

Use a closed binary-search interval:

left = 0
right = m * n - 1

The interval [left, right] represents every virtual index that could still contain target.

At each iteration:

1. Compute the midpoint.
2. Map it to (row, column).
3. Read the matrix value.
4. Compare it with target.
5. Remove the half that cannot contain the target.

The transitions are standard:

• If value == target, return True.

• If value < target, discard mid and everything before it:

  left = mid + 1
  

• If value > target, discard mid and everything after it:

  right = mid - 1
  

The invariant is the part worth remembering:

Before every iteration, if target exists, its virtual index lies inside [left, right].

The updates preserve that invariant because the virtual sequence is sorted. They also guarantee progress because mid is excluded from the next interval. If you write left = mid or right = mid, the interval may stop shrinking.

Prove correctness from global order

There are two claims to establish.

Claim 1: The virtual sequence is sorted

Each row is non-decreasing. At every row boundary, the first value of the next row is greater than the last value of the previous row.

Therefore, values never decrease while moving through the matrix in row-major order. The virtual sequence is sorted.

Claim 2: Each comparison safely removes a half

Suppose the midpoint maps to value x.

• If x < target, every earlier virtual index contains a value less than or equal to x, so none can equal target. Keeping only indices greater than mid is safe.
• If x > target, every later virtual index contains a value greater than or equal to x, so none can equal target. Keeping only indices less than mid is safe.
• If x == target, the target has been found.

The invariant remains true after each update. When the loop ends, left > right, so no virtual index remains in the candidate interval. The invariant then tells us that the target cannot exist. Returning False is sound.

This proof depends on the exact global-order contract. Do not silently apply it to every problem described as a “sorted matrix.”

Dry-run a successful and failed search

Use this matrix:

[
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]

It has 3 * 4 = 12 cells, so virtual indices range from 0 to 11.

For target = 16:

left	right	mid	row	column	value	action
0	11	5	1	1	11	Too small; set left = 6
6	11	8	2	0	23	Too large; set right = 7
6	7	6	1	2	16	Found

For target = 13, the same mapping produces:

left	right	mid	row	column	value	action
0	11	5	1	1	11	Too small; set left = 6
6	11	8	2	0	23	Too large; set right = 7
6	7	6	1	2	16	Too large; set right = 5

Now left = 6 and right = 5. The interval is empty, so return False.

When debugging, ask one question after every update:

Can the target still be represented by at least one virtual index inside the new interval?

If the answer is no, the update discarded too much. If the interval did not shrink, the update did not discard enough.

Implement the Python solution directly

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    rows = len(matrix)
    cols = len(matrix[0])

    left = 0
    right = rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2

        row = mid // cols
        column = mid % cols
        value = matrix[row][column]

        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

The supplied constraints guarantee at least one row and one column, so matrix[0] is valid for this exact problem contract.

Each variable has a precise job:

• left and right bound the remaining virtual candidate indices.
• mid selects the next virtual index to test.
• mid // cols reconstructs its row.
• mid % cols reconstructs its column.
• value is the actual matrix element used for the sorted comparison.

The implementation is intentionally plain. A helper for coordinate conversion would not improve the algorithm, and flattening the matrix would violate the constant-space goal. In an interview, visible state is an advantage: the code should expose the mapping and the invariant rather than hide them behind abstraction.

Verify complexity and test the failure points

There are m * n virtual cells. Binary search halves the candidate interval after each comparison, so the number of iterations is:

O(log(mn))

Each iteration performs constant-time arithmetic and one matrix lookup. No second data structure is created, so extra space is:

O(1)

Test the boundaries that attack the implementation, not just the happy path:

• A 1 x 1 matrix with the target present.
• A 1 x 1 matrix with the target absent.
• A single row.
• A single column.
• The first cell.
• The last cell.
• A target smaller than every value.
• A target larger than every value.
• The first value of a later row.
• The last value of an earlier row.
• Negative values.
• Duplicate values within a row.

The most common failures are mechanical:

• Dividing by rows instead of cols.
• Using m * n as the inclusive right bound instead of m * n - 1.
• Updating left = mid or right = mid, which may stall.
• Copying the matrix before searching.
• Assuming that row sorting alone creates one globally sorted sequence.
• Adding an empty-matrix branch without checking whether the problem contract already rules it out, then letting defensive code obscure the actual reasoning.

Before submitting, run this checklist:

1. Have you proved row-major global ordering?
2. Does every virtual index map to row = index // cols and column = index % cols?
3. Does [left, right] contain every possible target index?
4. Does every comparison remove mid and one full half of the interval?
5. Does the implementation avoid copying the matrix?

The transferable rule is simple: when structured two-dimensional data has monotonic row-major order, search the virtual one-dimensional indices and map each probe back to coordinates. For an unfamiliar problem, name the candidate interval, prove that the mapping preserves order, state the invariant, and verify that every comparison eliminates half the search space.