Search in a Sorted Matrix

You are given a square matrix of size n × n in which each row and each column is sorted in ascending order. Your task is to determine whether a given target integer exists in the matrix.

The challenge is to design an efficient algorithm (with a worst-case time complexity of O(n)) that can search the matrix for the target.

Note:

• The matrix may be empty or contain a single element.
• If the matrix is non-empty, then every row and every column is sorted in increasing order.
• If there are no elements in the matrix, the answer is automatically False.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains a single integer T representing the number of test cases.
• For each test case:
• The first line contains an integer n (if n = 0, the matrix is empty; if n > 0, the matrix has n rows and n columns).
• If n > 0, the next n lines each contain n space-separated integers representing the rows of the matrix.
• The next line contains an integer target which is the number to search for in the matrix.

outputFormat

For each test case, output a single line to standard output (stdout) with either True if the target exists in the matrix, or False otherwise.

1
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