Write an efficient algorithm that searches for a value target in an m × n integer matrix where each row is sorted left-to-right and each column is sorted top-to-bottom.
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5truesame matrix, target = 20falser=0, c=cols-1r < rows and c ≥ 0m[r][c] == target → return true (found!)m[r][c] > target → move left (c--), eliminating columnm[r][c] < target → move down (r++), eliminating rowfalseThe top-right corner is a unique decision point: values increase downward (via column sort) and decrease leftward (via row sort). So from any position we can always eliminate an entire row or column in a single comparison — just like a 2D binary search. Starting anywhere else would give us two "larger" directions or two "smaller" directions, making the choice ambiguous.
Checking every cell is O(m) times n. Binary searching each row is better, but still O(m) log n.
Start at the top right corner. Everything to its left is smaller, and everything below it is bigger. So if the value is too big, move left, and if it is too small, move down. Each step removes a whole row or a whole column.
Start at a corner where one move goes up in value and the other goes down. Top right: too big, go left. Too small, go down.
Run the animation above on your own input, or watch the 1:16 video explanation of Search a 2D Matrix II with a dry run and Java code.