publicbooleansearchMatrix(int[][] matrix, int target) { if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { returnfalse; } introw= matrix.length, col = matrix[0].length; return searchRect(matrix, target, 0, 0, col - 1, row - 1); }

privatebooleansearchRect(int[][] matrix, int target, int left, int up, int right, int down) { if (left > right || up > down) { returnfalse; // this submatrix has no height or no width } if (target < matrix[up][left] || target > matrix[down][right]) { returnfalse; // "target" is already larger than the largest or the smallest element } intmid= left + (right - left) / 2; // Locate "row" such that matrix[row - 1][mid] < target < matrix[row][mid] introw= up; while (row <= down && matrix[row][mid] <= target) { if (matrix[row][mid] == target) { returntrue; } row += 1; } return searchRect(matrix, target, left, row, mid - 1, down) || searchRect(matrix, target, mid + 1, up, right, row - 1); }