The challenge
Determine whether the target exists in a rectangular matrix viewed in row-major order.
Each row is ascending and its first value is greater than the previous row’s last. Empty matrices return false. r × c fits a signed 32-bit index.
Example
[[1, 3, 5], [7, 9, 11]], target = 9 → true.
Use the walkthrough below to inspect the input and each state change.
See Flattened matrix search, step by step
Inspect the comparison, the invariant, and the next boundary.
Inclusive candidate indicestarget = 9
| r / c | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1[0] | 3[1] | 5[2] |
| 1 | 7[3] | 9[4] | 11[5] |
Current comparisonResolved positionNumbers below = indices
- Left
- 0
- Middle
- —
- Right
- 5
Step 01 / 4
Start with the candidate indices
The retained interval contains the answer whenever it exists. Watch why each comparison can discard one side.
left = 0; right = 5Recorded result so far
Not resolved
View exact input
Matrix: [[1,3,5],[7,9,11]] · target = 9
Put it into code
The matrix is globally sorted when read row by row. Search virtual indices without allocating a flattened copy.
Indices are zero-based. C++ uses C++17 or later.
def search_matrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
left = mid + 1
else:
right = mid - 1
return False#include <vector>
bool search_matrix(const std::vector<std::vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int cols = static_cast<int>(matrix[0].size());
int left = 0, right = static_cast<int>(matrix.size()) * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) return true;
if (value < target) left = mid + 1;
else right = mid - 1;
}
return false;
}