Search in Sorted Matrix

You are given a matrix of integers where each row is sorted in ascending order and each column is also sorted in ascending order. Your task is to determine whether a given target integer exists in the matrix.

The algorithm should make use of the ordering properties of the matrix to achieve an efficient solution. In particular, the following strategy can be used: start at the top-right corner and, at each step, compare the current element \(matrix[i][j]\) with the target. If \(matrix[i][j] > target\), move left; if \(matrix[i][j] < target\), move down; if equal, the target is found.

Time Complexity: \(O(m+n)\), where \(m\) is the number of rows and \(n\) is the number of columns.

inputFormat

The input is given via standard input (stdin). The first line contains two integers \(m\) and \(n\), which represent the number of rows and columns in the matrix respectively.

If \(m > 0\), the next \(m\) lines each contain \(n\) space-separated integers, representing the rows of the matrix. Finally, the last line contains an integer \(target\), which is the number you need to search for in the matrix.

outputFormat

Output a single line to standard output (stdout) containing either True if the target exists in the matrix, or False otherwise.

5 5
1 4 7 11 15
2 5 8 12 19
3 6 9 16 22
10 13 14 17 24
18 21 23 26 30
5

True