Search a 2D Matrix

The Idea

Rows grow left to right and columns grow top to bottom, but the matrix is not one sorted list. Stand at the top-right corner instead. That cell is the largest in its row and the smallest in its column. Too big, and the whole column is too big — step left. Too small, and the whole row is too small — step down. Each move deletes an entire line, so the walk is m + n steps.

Real-World Example

A seating chart priced by row and by seat, both rising. An usher looking for a given price starts at the aisle end of the front row and walks one way or the other, never doubling back.

The Code

def search(matrix, target):
    r, c = 0, len(matrix[0]) - 1     # top-right corner
    while r < len(matrix) and c >= 0:
        v = matrix[r][c]
        if v == target:
            return (r, c)
        if v > target:
            c -= 1                   # that whole column is too big
        else:
            r += 1                   # that whole row is too small
    return None

print(search([[1, 4, 7], [8, 9, 12], [13, 15, 20]], 9))   # (1, 1)