Explanation
To search for a target value in a row-wise and column-wise sorted matrix (also known as Young Tableau search), we can start from either the top-right corner (row=0,col=N−1) or the bottom-left corner (row=N−1,col=0).
Algorithm Steps (Starting from Top-Right Corner):
If current element == target: Return found.
If current element > target: Move left (col=col−1) because all elements in the current column below this are even larger.
If current element < target: Move down (row=row+1) because all elements in the current row to the left are even smaller.
Complexity Analysis:
In each step, we eliminate either one row or one column.
At most, we can move N steps down and N steps left before reaching the boundary of the matrix.
Therefore, the maximum number of comparisons is N+N=2N.
Optimal Worst-case Time Complexity=O(N)
