Each row is sorted, and the first number of each row is bigger than the last number of the row before. Return true if the target is in the matrix.
DSA Animator › DSA Revision › Matrix › Search a 2D Matrix
Remember: a matrix sorted row after row is one long sorted array. Divide and mod by the column count to find the cell. The video solves Search a 2D Matrix (LeetCode 74, Medium) with the Binary Search pattern from the Matrix topic, and you can replay every step in the interactive Search a 2D Matrix animation.
Each row is sorted, and the first number of each row is bigger than the last number of the row before. Return true if the target is in the matrix.
In this 3 by 4 matrix, the target 3 is present, at row 0, column 1.
Checking every cell is O of m times n. But the rules mean the whole matrix is one sorted list, read row by row.
Binary search over positions 0 to m times n minus 1. Turn a position into a cell with row equal to position divided by the number of columns, and column equal to position mod the number of columns.
Low is 0 and high is 11, so mid is 5, which is row 1, column 1, holding 11. 11 is bigger than 3, so high becomes 4. Mid is 2, row 0, column 2, holding 5, still bigger, so high becomes 1. Mid is 0, holding 1, which is smaller, so low becomes 1. Mid is 1, holding 3, which is the target.
In code, set low to 0 and high to m times n minus 1. Compute mid, and read the matrix at mid divided by n and mid mod n. Return true on a match, or move low or high like a normal binary search. It's O of log of m times n time and O of 1 space.
Remember: a matrix sorted row after row is one long sorted array. Divide and mod by the column count to find the cell.