Search a 2D Matrix

Problem

You are given an m x n matrix of integers with two properties: every row is sorted in ascending order, and the first element of each row is strictly greater than the last element of the row above it. In other words, reading the matrix row by row yields one sorted list. Given an integer target, return True if it appears in the matrix and False otherwise, using logarithmically many cell reads.

• The matrix has between 1 and 500 rows and between 1 and 500 columns.
• Cell values and target are integers between -1,000,000 and 1,000,000.

Examples

• matrix = [[2, 6, 9, 14], [18, 21, 27, 33], [40, 45, 52, 58]], target = 27 → True.
• matrix = [[2, 6, 9, 14], [18, 21, 27, 33], [40, 45, 52, 58]], target = 24 → False; 24 would sit between 21 and 27 but is absent.
• matrix = [[5]], target = 8 → False. A 1x1 matrix still has to be handled by the same loop.

Hints

1. If you concatenated the rows, what would the resulting list look like?
2. You do not need to actually build that list. Can you map a position in the virtual list back to a row and column?
3. One binary search over indices 0 .. m*n - 1, translating mid to (mid // n, mid % n).