ASAPUtils
The signal
Every row is sorted and each row starts after the previous row ends. The whole matrix is globally sorted in row-major order. The two-dimensional storage is an indexing detail, not an algorithmic obstacle.
The index mapping
With cols columns, virtual flat index k maps to:
row = floor(k / cols)
col = k % cols
For four columns, flat index 6 is row 1, column 2. The value is matrix[1][2].
Optimal solution
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows = matrix.size(), cols = matrix[0].size();
int l = 0, r = rows * cols - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) return true;
if (value < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
function searchMatrix(matrix, target) {
const rows = matrix.length, cols = matrix[0].length;
let l = 0, r = rows * cols - 1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2);
const value = matrix[Math.floor(mid / cols)][mid % cols];
if (value === target) return true;
if (value < target) l = mid + 1;
else r = mid - 1;
}
return false;
}
Why it works
Virtual indices preserve the exact order produced by reading rows left-to-right, top-to-bottom. Therefore comparing one virtual middle value proves the same half-elimination facts as an ordinary sorted array.
Complexity
There are m*n virtual candidates, so time is O(log(m*n)); the coordinate calculation is O(1).
No flattened copy is created, so extra space is O(1).
Traps
- Using
mid / rowsinstead ofmid / cols. - Forgetting
Math.floorin JavaScript. - Physically flattening the matrix, spending unnecessary O(mn) time and space.
- Applying this method when rows overlap in value. If only rows and columns are independently sorted, use the top-right staircase walk instead.
Blank re-solve prompt
Search a globally row-major-sorted matrix in O(log(mn)) and O(1) space. Derive both coordinate formulas before writing the loop.