This problem follows the Binary Search on Matrix pattern, commonly found in the Binary Search category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Treat the 2D matrix as a flattened sorted array. Binary search with index conversion.
The 2D-to-1D index mapping (mid // cols, mid % cols) lets you apply standard binary search without flattening the matrix.
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
val = matrix[mid // cols][mid % cols]
if val == target: return true
elif val < target: left = mid + 1
else: right = mid - 1
return falsePractice Search a 2D Matrix and similar Binary Search problems with flashcards. Build pattern recognition through active recall.
Practice this problem