71. Search a 2D Matrix

Because each row's first element exceeds the previous row's last, the whole matrix reads as one sorted sequence. Binary search over the virtual index range [0, m*n) and map each mid index back to a (row, col) with divide and modulo.

Idea

The two properties together mean that if you read the matrix row by row, left to right, you get a single sorted list. So we can binary search the range of flat indices 0 .. m*n-1 without actually flattening anything — index mid maps to cell (mid // n, mid % n).

Algorithm

1. lo = 0, hi = m*n - 1.
2. While lo <= hi:
   • mid = (lo + hi) // 2; read val = matrix[mid // n][mid % n].
   • If val == target → return true.
   • If val < target → search the right half (lo = mid + 1).
   • Else → search the left half (hi = mid - 1).
3. If the range empties, the target isn't present → return false.

Worked example: target = 3 in [[1,3,5,7],[10,11,16,20],[23,30,34,60]] (m=3, n=4)

• lo=0, hi=11, mid=5 → cell (1,1)=11 > 3 → hi=4.
• lo=0, hi=4, mid=2 → cell (0,2)=5 > 3 → hi=1.
• lo=0, hi=1, mid=0 → cell (0,0)=1 < 3 → lo=1.
• lo=1, hi=1, mid=1 → cell (0,1)=3 == 3 → true.

Complexity

• Time: O(log(m·n)) — one binary search over all cells.
• Space: O(1).

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int val = matrix[mid / n][mid % n];
            if (val == target) {
                return true;
            } else if (val < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return false;
    }
}