Search a 2D Matrix
MediumBinary Search
You are given an m x n integer matrix with two properties:
- each row is sorted in non-decreasing order, and
- the first value of each row is greater than the last value of the row above it.
Reading the rows left to right, top to bottom therefore gives one sorted list. Given an integer target, return True if it appears anywhere in matrix and False otherwise.
Aim for O(log(m * n)) time.
Example 1
- Input:
- matrix = [[1,3,5],[8,10,12]], target = 10
- Output:
- True
- Explanation
- 10 sits in the second row. Because the rows run in order, the whole matrix reads as one sorted sequence.
Example 2
- Input:
- matrix = [[1,3,5],[8,10,12]], target = 6
- Output:
- False
- Explanation
- 6 would fall between the 5 that ends the first row and the 8 that starts the second, so it is absent.
Example 3
- Input:
- matrix = [[1],[3],[5]], target = 4
- Output:
- False
- Explanation
- Single-column rows work the same way, and 4 falls between 3 and 5.
Constraints
m == matrix.length,n == matrix[i].length1 <= m, n <= 100-10^4 <= matrix[i][j], target <= 10^4- Each row is non-decreasing, and each row's first value is greater than the previous row's last value