Search a 2D Matrix II

The Sorted Vault keeps its treasure behind a wall of numbered locks, m rows by n columns. The wall follows two rules: every row goes up from left to right, and every column goes up from top to bottom. Equal numbers can sit next to each other. The knight has to say, fast, whether a given number is on the wall at all.

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

grid = [[ 3,  9, 15, 22, 30, 47],
        [ 5, 12, 19, 27, 36, 48],
        [ 8, 16, 25, 33, 42, 55],
        [11, 20, 29, 39, 50, 61],
        [14, 24, 35, 45, 57, 68],
        [18, 28, 40, 52, 64, 75]]
search_matrix(grid, 42)    # True
search_matrix(grid, 26)    # False
search_matrix(grid, 75)    # True
search_matrix([[7]], 3)    # False

Unlike a grid read in one long sorted line, a row here can end with a bigger number than the next row starts with (47 ends row 0, 5 starts row 1), so you can't treat it as one sorted list.

• 1 <= m, n <= 1000; values are in [-10^9, 10^9].
• The tests run thousands of lookups on one big grid. Scanning every cell (including in on each row) is far too slow. Aim for O(m + n) per lookup.
• C++ / Java: you write searchMatrixAll(grid, targets), which returns searchMatrix(grid, t) for every t in targets, in order. Write searchMatrix as a helper and call it in a loop.