Search a 2D Matrix

Each row sorted ascending, first element of each row greater than the last element of the previous row (so the whole matrix reads like one long sorted array). (LeetCode problem)

Brute force: scan every cell — O(n × m).

Better: find the row whose range contains target (matrix[i][0] <= target <= matrix[i][last]), then binary search within that row — O(n) + O(log m).

Optimal — treat it as one flattened 1D array: for an n × m matrix, a flat index maps to row = index / m, col = index % m. Binary search directly over [0, n*m - 1] without actually flattening.

public boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length;
    int m = matrix[0].length;
    int low = 0, high = n * m - 1;

    while(low <= high){
        int mid = (low + high) / 2;
        int row = mid / m, col = mid % m;

        if(matrix[row][col] == target) return true;
        else if(matrix[row][col] < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

Time: O(log(n × m)). Space: O(1).