You are given a grid of numbers matrix with m rows and n columns. It has two properties:
- Each row is sorted from small to big.
- The first number of a row is bigger than the last number of the row above it.
Return true if target is in the grid, otherwise return false. Try to find it fast. A binary search works well, because the grid read row by row is one sorted list.
Examples
Example 1:
Input: matrix = [[2,4,6],[8,10,12],[14,16,18]], target = 10
Output: true
Explanation: The number 10 is in the middle row.
Example 2:
Input: matrix = [[2,4,6],[8,10,12],[14,16,18]], target = 11
Output: false
Explanation: 11 would sit between 10 and 12, but it is not in the grid.
Example 3:
Input: matrix = [[5]], target = 5
Output: true
Explanation: A grid with one cell.