Given an m×n matrix where each row is sorted left to right, and the first number of each row is larger than the last number of the previous row, return whether target exists anywhere in the matrix.
Because rows are individually sorted and stacked in increasing order, the whole matrix behaves like one flattened sorted array of length m×n.
A flat index converts to a (row, col) pair with divmod against the row width.
One binary search over the flattened index range replaces a separate search per row.
Step-by-Step Analysis
Let m, n be the matrix's dimensions; set left = 0, right = m*n - 1.
While left has not passed right: compute mid, then convert it to row, col via divmod(mid, n).
Compare matrix[row][col] to the target; if equal, return true.
If the matrix value is smaller than the target, search the upper half of the flat range; otherwise search the lower half.
If the loop ends without a match, return false.
Complexity
Time: O(log(m·n)) — Space: O(1)
Code
def searchMatrix(matrix: list[list[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
left, right = 0, m * n - 1
while left <= right:
mid = left + (right - left) // 2
row, col = divmod(mid, n)
val = matrix[row][col]
if val == target:
return True
elif val < target:
left = mid + 1
else:
right = mid - 1
return False
Code Explanation
How the solution above works, piece by piece.
Treat the m × n matrix as a single sorted array of length m * n: positions 0 to m*n − 1.
Run ordinary binary search on those positions.
row, col = divmod(mid, n): position ÷ row length gives the row, the remainder gives the column.
Compare and move left or right exactly as in plain binary search.
O(log(m·n)) time and O(1) space: no copying into a real list.
Visual Walkthrough
Running it on the 3 × 4 example with target = 3:
Rows are sorted and each row starts after the previous one ends, so reading row by row gives one sorted list of 12. divmod(mid, n) turns a list position back into (row, column) without building the list.