DSA Searching a 2D Matrix

The problem

Search a 2D Matrix looks for a target value in a grid of numbers. Each row is sorted, and each row starts with a value above the last value of the row before it. The answer is the row and column of the target, or None when the target is absent.

The cases below are the ones this article tests every solution against. They include the first cell, the last cell, and a gap value that is not in the grid.

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
cases = [(16, (1, 2)), (13, None), (60, (2, 3)), (1, (0, 0))]
for target, expected in cases:
    print("target", target, "position:", expected)

Read one row at a time. The value 13 would sit between 11 and 16, but no cell holds it. A correct search must report that absence, not the nearest cell.

Intuition: read the grid like a book

The first idea reads the grid left to right, row by row, until the target appears. Reading order is simple to write. It also visits every cell before the target, wherever the target sits.

The grid hides a stronger fact. Read in book order, the cells form one long sorted list. The intuition ignores that order, and the next count shows what ignoring it costs.

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
visited = 0
found = None
for r in range(len(matrix)):
    for c in range(len(matrix[0])):
        visited += 1
        if matrix[r][c] == 16:
            found = (r, c)
            break
    if found is not None:
        break
print("position:", found)
print("cells visited:", visited, "of", len(matrix) * len(matrix[0]))

Seven cells were visited for a target in the second row. A target in the last cell would visit all twelve. The scan pays for position, not for difficulty.

Brute force: check every cell, counted

The brute force is the book-order scan, written as a function. Two nested loops generate each cell once. A counter records every comparison.

The absent case is the expensive one. Only a full sweep of all twelve cells proves that 13 is not in the grid.

def search_brute(matrix, target):
    checked = 0
    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            checked += 1
            if matrix[r][c] == target:
                return (r, c), checked
    return None, checked

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
pos, checked = search_brute(matrix, 16)
print("target 16 ->", pos, "comparisons:", checked)
pos, checked = search_brute(matrix, 13)
print("target 13 ->", pos, "comparisons:", checked)
pos, checked = search_brute(matrix, 60)
print("target 60 ->", pos, "comparisons:", checked)

The last cell costs all twelve comparisons. Nothing in the scan uses the sorted order. That unused order is exactly what the optimal solution spends.

The optimal solution: one binary search over a flat index

A flat index numbers the cells in book order from zero, and dividing a flat index by the column count gives its row while the remainder gives its column. That one sentence turns the grid into a sorted list that a binary search can halve.

The search never builds the flat list. It computes the row and column of the middle flat index on each step and reads that one cell.

def search(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0])
    lo = 0
    hi = rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return (mid // cols, mid % cols)
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
cases = [(16, (1, 2)), (13, None), (60, (2, 3)), (1, (0, 0))]
for target, expected in cases:
    result = search(matrix, target)
    print("target", target, "->", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. A second route finds the row first and then searches inside that row. It makes the same halvings in two stages and lands on the same cells.

Walkthrough: target 16 in the twelve-cell grid

The walk tracks the flat range and the middle cell at each step. Each comparison discards half the range. Three steps reach the target.

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
cols = len(matrix[0])
target = 16
lo = 0
hi = len(matrix) * cols - 1
step = 0
while lo <= hi:
    step += 1
    mid = (lo + hi) // 2
    row = mid // cols
    col = mid % cols
    value = matrix[row][col]
    print("step", step, "- range", lo, "to", hi, "- flat", mid, "is row", row, "col", col, "value:", value)
    if value == target:
        print("found at row", row, "col", col)
        break
    if value < target:
        lo = mid + 1
    else:
        hi = mid - 1

The first middle cell holds 11, so every flat index up to 5 is discarded at once. The second middle overshoots at 23. The range left between them holds two cells, and the next step lands on the target.

Complexity

The brute force compares up to every one of the m times n cells, so its time is O(m times n). The flat search halves the cell count on each step, so its time is O(log of m times n).

Both searches store only bounds and counters, so their extra space is O(1). The flat list exists only as arithmetic, never as data.

def binary_count(cells):
    steps = 0
    size = cells
    while size >= 1:
        steps += 1
        size //= 2
    return steps

for rows, cols in [(3, 4), (10, 10), (100, 100)]:
    cells = rows * cols
    print("grid", rows, "x", cols, "cells:", cells, "worst brute comparisons:", cells, "worst binary steps:", binary_count(cells))

At ten thousand cells the scan can pay ten thousand comparisons. The halving search pays fourteen steps. The gap comes from discarding half the grid per step, not from reading cells faster.

Edge cases and pitfalls

The classic mistake is dividing by the row count instead of the column count. The two counts differ in a non-square grid, and the wrong divisor lands on the wrong cell while still looking plausible. The cases in this article use a 3 by 4 grid precisely so that mistake shows.

An empty grid has no cells to search. The search must return None before any division happens, because the column count of an empty grid is undefined.

def search(matrix, target):
    if not matrix or not matrix[0]:
        return None
    rows = len(matrix)
    cols = len(matrix[0])
    lo = 0
    hi = rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]
        if value == target:
            return (mid // cols, mid % cols)
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

matrix = [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 60],
]
print("empty grid:", search([], 5))
print("single cell hit:", search([[8]], 8))
print("single cell miss:", search([[8]], 9))
print("below the smallest:", search(matrix, 0))
print("above the largest:", search(matrix, 99))
print("last cell:", search(matrix, 60))

Targets outside the grid's range end the search by emptying the range. No special case handles them. The bounds crossing is itself the not-found signal.