Search a 2D Matrix

You are given an m x n integer matrix with two properties:

• Each row is sorted in ascending order from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Return true if target appears in the matrix and false otherwise.

Input / output

• Input: matrix: int[][], target: int
• Output: boolean

Examples

1. matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 returns true.
2. matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 returns false.
3. matrix = [[1]], target = 1 returns true.

Constraints

• 1 <= m, n <= 100
• -10000 <= matrix[i][j], target <= 10000
• The matrix satisfies the two sorting properties above.

Edge cases

• A single-cell matrix.
• Targets smaller than the first cell or larger than the last cell.

Target complexity

• Aim for O(log(m * n)) time and O(1) extra space.

Hints

1. Because the rows chain together, the whole matrix behaves like one sorted array.
2. Map a flat index i to matrix[i / n][i % n] to run a single binary search.

Follow-up If only rows (but not the row-boundaries) were sorted, what search strategy would you use instead?