Search a 2D Matrix

You get a grid of integers, matrix, with m rows and n columns. You also get an integer target.

Return True if matrix contains target, and False if it doesn't.

The grid is sorted in two ways:

• Each row goes from smallest to largest. Equal neighbors are allowed.
• Each row starts with a value bigger than the last value of the row above.

The grid is a list of rows. Each row is a list of integers. Rows are counted from 0 at the top, columns from 0 at the left.

Example 1:

Input: matrix = [
  [2, 4, 9],
  [12, 15, 18],
  [21, 26, 30],
  [33, 40, 47]
], target = 26
Output: True
Explanation: 26 is in row 2, column 1.

Example 2:

Input: matrix = [
  [2, 4, 9],
  [12, 15, 18],
  [21, 26, 30],
  [33, 40, 47]
], target = 20
Output: False
Explanation: Row 1 ends with 18, and row 2 starts with 21.
20 would sit between them, but it isn't in the grid.

Example 3:

Input: matrix = [
  [-7],
  [-3],
  [0],
  [5]
], target = -3
Output: True
Explanation: The grid has a single column.
-3 is in row 1.

Constraints:

• 1 to 1,000 rows.
• 1 to 1,000 columns.
• Every value and target are from -10⁹ to 10⁹.
• All rows have the same length.
• The grid follows the two rules above.