You are given an m × n grid of integers matrix with two properties: each row is sorted in
increasing order, and each row's first number is greater than the last number of the row above.
So reading the rows one after another gives a single sorted list.
Return true if target is in matrix, and false otherwise, in O(log(m · n)) time.
Example 1
- Input
- matrix = [[1, 4, 6], [9, 12, 15], [20, 25, 31]], target = 12
- Output
- true
Example 2
- Input
- matrix = [[1, 4, 6], [9, 12, 15], [20, 25, 31]], target = 7
- Output
- false
Constraints
- 1 ≤ m, n ≤ 100
- Every number, and
target, is between −10⁴ and 10⁴.
Show the pattern
Binary search
Read row after row, the grid is one sorted list, so a single binary search over positions 0 to m·n − 1 finds the target; division turns each position into a row and a column.
See binary search in a visualiserShow the approach
Reading the rows in order gives one sorted list of m · n numbers, so binary search it without
building it. Keep lo = 0 and hi = m · n − 1. The number at position mid is
matrix[mid // n][mid % n]: the row is how many full rows come before it, and the column is
what's left over. Compare it with target and halve the range, as in an ordinary binary search.
Searching for the right row first, then within that row, also takes O(log m + log n), the same.
Time: O(log(m · n)) · Space: O(1)