The matrix rows are sorted left-to-right and each row starts after the last row ends — so the whole grid is one big sorted sequence. Treat it as a flat array of length m * n and run a single binary search; map the flat midpoint back to (mid / n, mid % n) to read the real cell.
Given an m × n integer matrix where each row is sorted left-to-right and the first integer of each row is greater than the last integer of the previous row, decide whether target appears in the matrix. Return true or false.
Concrete example. Matrix:
[[ 1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
Target = 3 → true (row 0, col 1). Target = 13 → false.
m * n numbers. That means we can binary-search on flat index 0 to m * n − 1 and convert any midpoint mid to a real cell with row = ⌊mid / n⌋, col = mid % n. One pass, no 2D logic.lo = 0, hi = m * n − 1. These are flat indices into the conceptual 1D array.mid = (lo + hi) >>> 1. Use unsigned right-shift to safely halve without overflow.row = ⌊mid / n⌋, col = mid % n. Division gives the row, remainder gives the column.matrix[row][col] === target → return true. If less than target → move lo = mid + 1 (target is to the right). If greater → move hi = mid − 1 (target is to the left).lo > hi, target is not present — return false.mid / n without Math.floor (or integer division) produces a fractional row index and silently reads undefined. Always floor the division. Likewise, forgetting the % n for the column and reading the entire row instead is a common copy-paste bug.Only lo, hi, and mid are needed — constant extra space. No copy of the matrix is made.
Staircase search alternative.LeetCode 240 relaxes the constraint (rows independently sorted, but first element not necessarily greater than previous row's last). For that problem the standard trick is to start at the top-right corner and walk left or down. For this problem (LC 74), the flat binary search is strictly better at O(log m·n).
12. Binary search on indices 0–11.1function searchMatrix(matrix: number[][], target: number): boolean {2▶ const m = matrix.length;3▶ const n = matrix[0].length;4▶ let lo = 0;5▶ let hi = m * n - 1;67 while (lo <= hi) {8 const mid = (lo + hi) >>> 1; // integer midpoint9 const val = matrix[Math.floor(mid / n)][mid % n]; // map flat → 2D1011 if (val === target) return true;12 if (val < target) lo = mid + 1; // search right13 else hi = mid - 1; // search left14 }15 return false;16}
function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length;
const n = matrix[0].length;
let lo = 0;
let hi = m * n - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1; // integer midpoint
const val = matrix[Math.floor(mid / n)][mid % n]; // map flat → 2D
if (val === target) return true;
if (val < target) lo = mid + 1; // search right
else hi = mid - 1; // search left
}
return false;
}m and n once, then set lo = 0 and hi = m * n - 1. These are flat indices into the virtual 1D array the matrix secretly is.(lo + hi) >>> 1 is JavaScript's idiomatic way to compute ⌊(lo + hi) / 2⌋ without integer overflow — safer than (lo + hi) / 2 | 0 when values are large.Math.floor(mid / n) is the row (how many full rows fit before mid) and mid % n is the column (remainder within the row). This is the entire trick — everything else is plain binary search.lo past mid. Value too large ⇒ pull hi below mid. The loop exits when lo > hi.false.O(m + n) — still better than O(m · n).mid at the moment val === target and decode it with [Math.floor(mid / n), mid % n].if (!matrix.length || !matrix[0].length) return false before touching n.function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length;
const n = matrix[0].length;
let lo = 0;
let hi = m * n - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1; // integer midpoint
const val = matrix[Math.floor(mid / n)][mid % n]; // map flat → 2D
if (val === target) return true;
if (val < target) lo = mid + 1; // search right
else hi = mid - 1; // search left
}
return false;
}Ignore the sorted structure entirely: walk all m·n cells and return true the moment one equals target.
function searchMatrix(matrix: number[][], target: number): boolean {
for (const row of matrix) {
for (const val of row) {
if (val === target) return true;
}
}
return false;
}O(m·n). Because the grid reads as one big sorted sequence, binary search over the flat index range finds the target in O(log(m·n)) instead.| sorted matrix where each row follows the last | flat-index binary search: lo=0, hi=m*n-1 |
| map flat index to 2D cell | row = ⌊mid / n⌋, col = mid % n |
| globally sorted 2D grid, search for value | single O(log m·n) binary search |
| rows sorted independently but NOT globally chained | staircase search from top-right, O(m+n) |
function searchMatrix(matrix: number[][], target: number): boolean {
const m = matrix.length, n = matrix[0].length;
let lo = 0, hi = m * n - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1;
const val = matrix[Math.floor(mid / n)][mid % n];
if (val === target) return true;
if (val < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}m=3, n=4), what is the flat index of cell [2][1]?const val = matrix[mid / n][mid % n] sometimes returns undefined. What is the fix?