Search a sorted grid
A grid of integers matrix has m rows and n columns and is sorted in reading order, the order of words on a page: left to right along a row, then on to the next row. Two facts make that true. Along a row, values never go down from left to right (repeats are allowed). And the first value of each row is bigger than the last value of the row above it.
Report whether some cell holds target: return True if one does and False if none does.
Checking every cell gives the right answer but fails the speed test. Aim for O(log(m·n)) time.
matrix = [[1, 4, 7], [10, 13, 16], [20, 25, 30]], target = 13OutputTrue13 is in row 1, column 1.
matrix = [[1, 4, 7], [10, 13, 16], [20, 25, 30]], target = 8OutputFalseIn reading order, 8 would fall between 7, the end of row 0, and 10, the start of row 1. No cell holds it.
matrix = [[3, 5, 8, 12]], target = 3OutputTrueA grid can have a single row. 3 is its first cell.
1 ≤ m, n ≤ 6,500: the grid is never empty, and every row has n values.
Values and target are integers.
The speed test passes a 6,500 by 6,500 grid (42,250,000 cells) that computes each cell when you read it. It supports
len(matrix),matrix[r],len(matrix[r])andmatrix[r][c](negative indexes too) but not slicing. Reading every cell takes seconds.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.