Sample answer

• Make use of the given row number m and col number n
• we can place all rows in one row, indexing from 0 to the index of last element, lets call this index as mid. The values of elements are guaranteed to be ascending
• We can obtain the row index of the element by mid / n
• We can obtain the col index of the element by mid % n

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

        int left = 0;
        int right = n * m - 1;

        while (left <= right) {
            int mid = left + (right-left)/2;

            int val = matrix[mid/n][mid%n];

            if (val == target) return true;
            if (val < target) left = mid + 1;
            if (val > target) right = mid - 1;
        }

        return false;
    }
}

My own attempt

• Time complexity is O(m + logn) , we can optimise it to O(logm + logn) by performing binary search to find the desired row

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int[] row=matrix[0];
        int left=0;
        int right=matrix[0].length-1;

        for (int[] r:matrix) {
            if (r[right] >= target) {
                row = r;
                break;
            }
        }

        while (left <= right) {
            int mid = left + (right-left)/2;
            int midVal = row[mid];
            //System.out.println(midVal);

            if (midVal == target) return true;
            if (midVal > target) right = mid-1;
            if (midVal < target) left = mid + 1;
        }

        return false;
    }
}