Java Solution Worst Case O(m+n)
public boolean searchMatrix(int[][] matrix, int target) {\n        if(matrix==null ||matrix.length==0 ||matrix[0].length==0)\n            return false;\n       
    public boolean searchMatrix(int[][] matrix, int target) {\n        if(matrix==null ||matrix.length==0 ||matrix[0].length==0)\n            return false;\n        int i=0,j=matrix[0].length-1;\n        while(i<matrix.length && j>=0){\n            if(matrix[i][j] == target)\n                return true;\n            else if(matrix[i][j] < target)\n                i++;\n            else\n                j--;\n        }\n        return false;\n    }
[]