Search for a command to run...
Treat the 2D matrix as a 1D sorted array and apply binary search
Current step
Search for target 3 in a 3x4 matrix. Since rows are sorted and the first integer of each row is greater than the last integer of the previous row, we can treat it as a 1D sorted array of size 12.
Binary Search
1class Solution {2 searchMatrix(mat, target) {3 let n = mat.length;4 let m = mat[0].length;5 6 let low = 0, high = n * m - 1;7 8 while (low <= high) {9 let mid = Math.floor((low + high) / 2);10 11 let row = Math.floor(mid / m);12 let col = mid % m;13 14 if (mat[row][col] === target) return true;15 else if (mat[row][col] < target) low = mid + 1;16 else high = mid - 1;17 }18 19 return false; 20 }21}