Matrix Search in a Sorted 2D Array

You are given a 2D matrix in which each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Your task is to determine whether a given target value exists in the matrix.

The search algorithm should be efficient. One optimal approach is to start from the top-right corner of the matrix. If the current element equals the target, return true. If it is greater than the target, move one column to the left. Otherwise, move one row down. This process is repeated until the target is found or the search space is exhausted.

This problem is a common coding interview and competitive programming challenge. Make sure your solution reads input from stdin and writes output to stdout.

inputFormat

The first line contains two integers (r) and (c) denoting the number of rows and columns in the matrix. Each of the next (r) lines contains (c) space-separated integers representing a row of the matrix. The last line contains a single integer (t), which is the target value to search for.

outputFormat

Output true if the target value is found in the matrix; otherwise, output false.## sample

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