Search a 2D Matrix

A warehouse labels its shelves with ID numbers laid out in a grid of m rows and n columns. Reading the grid row by row, left to right and top to bottom, the IDs are strictly increasing: each row is sorted, and the first ID of a row is larger than the last ID of the row above it.

Write grid_contains(grid: list[list[int]], target: int) -> bool that returns True if target appears in the grid.

grid = [[2, 5, 9, 11],
        [14, 20, 21, 30],
        [33, 40, 47, 52]]
grid_contains(grid, 21)    # True
grid_contains(grid, 12)    # False  (it would sit between 11 and 14)
grid_contains(grid, 52)    # True
grid_contains([[7]], 3)    # False

• 1 <= m, n and m * n <= 10^6; values are in [-10^9, 10^9].
• The tests run thousands of lookups on one big grid, so each lookup must be O(log(m * n)). Scanning cells, or even scanning down the rows to find the right one, is too slow. Don't use in on a row or the bisect module.
• C++ / Java: you write gridContainsAll(grid, targets), which returns gridContains(grid, t) for every t in targets, in order, so the tests can run many lookups on one big grid. Write gridContains as a helper and call it in a loop.