Search a 2D Matrix II in Scala

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, left to right.
• Each column goes from smallest to largest, top to bottom.

Equal neighbors are allowed. A row's first value can be smaller than the last value of the row above.

The tests search the same grid for many targets, one call per target.

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

Example 1:

Input: matrix = [
  [3, 8, 12, 20],
  [5, 9, 15, 24],
  [7, 14, 18, 30]
], target = 15
Output: true
Explanation: 15 is in row 1, column 2.

Example 2:

Input: matrix = [
  [3, 8, 12, 20],
  [5, 9, 15, 24],
  [7, 14, 18, 30]
], target = 13
Output: false
Explanation: The grid has 12 and 14, but no 13.

Example 3:

Input: matrix = [
  [-6, -2, 0],
  [-4, 1, 1]
], target = -4
Output: true
Explanation: -4 is in row 1, column 0.
Row 1 starts with -4, but row 0 ends with 0.
The two rows overlap, and that's allowed.

Constraints:

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