Search a Sorted Grid

A grid of whole numbers is given as a list of rows. Every row is sorted from smallest to largest going right, and every column is sorted from smallest to largest going down. No number appears twice in the grid.

Write find_in_grid(grid, target) that returns the position of target as a tuple (row, col), or None if it is not in the grid.

Examples

grid = [[ 2,  5,  9, 14],
        [ 4,  7, 12, 20],
        [ 8, 11, 16, 25],
        [13, 18, 22, 30]]
find_in_grid(grid, 16)   # returns (2, 2)
find_in_grid(grid, 13)   # returns (3, 0)
find_in_grid(grid, 10)   # returns None

Constraints

• 0 to 500 rows and 0 to 500 columns; every row has the same length, and the grid can be [] or made of empty rows.
• Checking every cell works, but try to look at no more than about rows + columns cells: there is a walk through the grid that does it.