Search for a target in a matrix where each row is sorted left-to-right and each column top-to-bottom.
Start at the top-right corner: if the value equals the target you are done; if it is larger, move left (everything below in the column is larger); if smaller, move down. Each step eliminates a row or column, giving O(m + n) — far better than scanning every cell.
public static boolean searchMatrix(int[][] m, int target) {
if (m.length == 0) return false;
int r = 0, c = m[0].length - 1;
while (r < m.length && c >= 0) {
if (m[r][c] == target) return true;
if (m[r][c] > target) c--; else r++;
}
return false;
}function searchMatrix(m, target) {
if (m.length === 0) return false;
let r = 0, c = m[0].length - 1;
while (r < m.length && c >= 0) {
if (m[r][c] === target) return true;
if (m[r][c] > target) c--; else r++;
}
return false;
}def search_matrix(m, target):
if not m:
return False
r, c = 0, len(m[0]) - 1
while r < len(m) and c >= 0:
if m[r][c] == target:
return True
if m[r][c] > target:
c -= 1
else:
r += 1
return FalseThe staircase search is how you probe a sorted grid (e.g. a time x value table) without a full scan — a neat use of the two-way ordering.
Why start at the top-right corner rather than the top-left?