Searching in two dimensions

Let $M$ be an $nn$ integer matrix in which the entries of each row are sorted in increasing

order $($from left to right$)$ and the entries in each column are sorted in increasing order $($from

top to bottom$).$ Give an algorithm to find the position of an integer $x$ in $M,$ or to determine that

$x$ is not there. In the worst case, the algorithm should do a maximum of $O(n)$ comparisons.

Algorithms doing more comparisons get zero points.

Description of the algorithm

$(3$ points$)$

Brief justification why the algorithm is correct

$(1$ point$)$

Brief justification why the algorithm runs in $O(n)$ time

$(1$ point$)$