The given matrix is ordered both row-wise and column-wise, enabling a two-step binary search approach for efficient target lookup.

First, determine the correct row by comparing the first element of each row with the target. Use binary search to narrow down the candidate row where the target could reside. Once the row is identified, perform another binary search with in that row to locate the target value.

This method avoids scnaning all rows and reduces time complexity from O(m × n) to O(log m + log n), where m is the number of rows and n is the number of columns.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;

        // Step 1: Find the row using binary search on the first column
        int lowRow = 0;
        int highRow = rows - 1;
        while (lowRow < highRow) {
            int midRow = lowRow + (highRow - lowRow) / 2 + 1;
            if (matrix[midRow][0] > target) {
                highRow = midRow - 1;
            } else {
                lowRow = midRow;
            }
        }

        int targetRow = highRow;

        // Step 2: Find the column in the identified row
        int lowCol = 0;
        int highCol = cols - 1;
        while (lowCol < highCol) {
            int midCol = lowCol + (highCol - lowCol) / 2 + 1;
            if (matrix[targetRow][midCol] > target) {
                highCol = midCol - 1;
            } else {
                lowCol = midCol;
            }
        }

        return matrix[targetRow][lowCol] == target;
    }
}