Description
Decide whether target appears in a non-empty rectangular integer matrix. Every row is sorted, and each row's first number is larger than the previous row's last number.
Solution
def search_matrix(matrix, target):
columns = len(matrix[0])
left, right = 0, len(matrix) * columns - 1
while left <= right:
middle = (left + right) // 2
value = matrix[middle // columns][middle % columns]
if value == target:
return True
if value < target:
left = middle + 1
else:
right = middle - 1
return FalseExamples
Example 1
- Input
[[[1,3,5],[7,9,11]],9]- Output
true
9 is in the second row.
Example 2
- Input
[[[1,3,5],[7,9,11]],6]- Output
false
6 lies between rows but is absent.
Example 3
- Input
[[[1]],1]- Output
true
A one-cell matrix still works.
Approach
Treat the matrix as one sorted sequence. Binary-search flattened indices, converting an index to row and column by division and remainder using the column count.
Time & space
O(log(rc)) time and O(1) auxiliary space, where r and c are row and column counts.