Module 12 · Binary Search and Monotone Answer Spaces

118. Search a Row-Major Sorted Matrix

Interview · Download this solution · All solutions and shared helpers

Problem

Return whether target occurs in a rectangular matrix whose row-major sequence is globally nondecreasing. Each row is ordered and every row's first value is at least the previous row's last value. Empty matrices or zero columns return False.

Examples

Example 1

search_matrix([[1,3,5],[7,9,11]], 9)
=> True

Virtual index four maps to row one, column one.

Example 2

search_matrix([[1,3,5],[7,9,11]], 6)
=> False

Six lies between values but does not occur.

Example 3

search_matrix([], 1)
=> False

There is no virtual candidate interval.

Reveal the worked solution and reasoning

Why this mechanism works

The matrix is one sorted sequence stored in two dimensions. A virtual index mid maps to row mid//cols and column mid%cols. Search virtual boundaries without copying the matrix into a flat array.

State and boundaries

[left,right) is a candidate range in the virtual rows*cols sequence. divmod converts each midpoint into one matrix cell.

Protocol

Handle an empty matrix.
Set the virtual search interval to [0,rows*cols).
Map each midpoint to a row and column.
Apply exact binary-search comparison.
Return False on exhaustion.

Visualization

matrix [[1,3,5],[7,9,11]]
virtual [1,3,5,7,9,11]
mid=4 -> divmod(4,3)=(1,1) -> value 9

Python implementation

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols
    while left < right:
        mid = (left + right) // 2
        r, c = divmod(mid, cols)
        value = matrix[r][c]
        if value == target:
            return True
        if value < target:
            left = mid + 1
        else:
            right = mid
    return False

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

search_matrix([[1,3,5],[7,9,11]], 9)

L2 search_matrix: if not matrix or not matrix[0]:
matrix=[[1, 3, 5], [7, 9, 11]]; target=9

L4 search_matrix: rows, cols = len(matrix), len(matrix[0])
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3

L5 search_matrix: left, right = 0, rows * cols
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=0; right=6

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=0; right=6; mid=3

L8 search_matrix: r, c = divmod(mid, cols)
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=0; right=6; mid=3; r=1; c=0

L9 search_matrix: value = matrix[r][c]
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=0; right=6; mid=3; r=1; c=0; value=7

L13 search_matrix: left = mid + 1
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=6; mid=3; r=1; c=0; value=7

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=6; mid=5; r=1; c=0; value=7

... 2 intermediate state changes omitted ...

L15 search_matrix: right = mid
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=5; mid=5; r=1; c=2; value=11

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=5; mid=4; r=1; c=2; value=11

L8 search_matrix: r, c = divmod(mid, cols)
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=5; mid=4; r=1; c=1; value=11

L9 search_matrix: value = matrix[r][c]
matrix=[[1, 3, 5], [7, 9, 11]]; target=9; rows=2; cols=3; left=4; right=5; mid=4; r=1; c=1; value=9

Result: True. Virtual index four maps to row one, column one.

search_matrix([[1,3,5],[7,9,11]], 6)

L2 search_matrix: if not matrix or not matrix[0]:
matrix=[[1, 3, 5], [7, 9, 11]]; target=6

L4 search_matrix: rows, cols = len(matrix), len(matrix[0])
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3

L5 search_matrix: left, right = 0, rows * cols
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=6

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=6; mid=3

L8 search_matrix: r, c = divmod(mid, cols)
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=6; mid=3; r=1; c=0

L9 search_matrix: value = matrix[r][c]
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=6; mid=3; r=1; c=0; value=7

L15 search_matrix: right = mid
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=3; mid=3; r=1; c=0; value=7

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=0; right=3; mid=1; r=1; c=0; value=7

... 3 intermediate state changes omitted ...

L7 search_matrix: mid = (left + right) // 2
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=2; right=3; mid=2; r=0; c=1; value=3

L8 search_matrix: r, c = divmod(mid, cols)
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=2; right=3; mid=2; r=0; c=2; value=3

L9 search_matrix: value = matrix[r][c]
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=2; right=3; mid=2; r=0; c=2; value=5

L13 search_matrix: left = mid + 1
matrix=[[1, 3, 5], [7, 9, 11]]; target=6; rows=2; cols=3; left=3; right=3; mid=2; r=0; c=2; value=5

Result: False. Six lies between values but does not occur.

Why the solution is correct

Row-major global order makes the virtual sequence sorted. The index mapping is a bijection between virtual positions and cells, preserving that order. Therefore the usual exact-search exclusion proof applies without any physical flattening.

Time and space

O(log(rows*cols+1)) time and O(1) auxiliary space.

Common mistakes

Merely sorting each row independently is not enough for this method. Dividing by the row count instead of the column count maps positions incorrectly.

Reasoning card

State: [left,right) is a candidate range in the virtual rows*cols sequence. divmod converts each midpoint into one matrix cell.

Invariant: The virtual candidate interval contains the target if present.

Decision to rehearse: Map virtual index to row/column.

Finish: Return False on exhaustion

Transfer exercise

When rows and columns are individually sorted but row-major order is not, derive a top-right staircase search instead.