# Algorithm to check if number x exists in matrix

I have the task to develop an algorithm which checks if a specific number x exists in an int-array[][]. Further the 2-dim array entries have following terms:

$$array[i][j] \leq array[i][j+1] \space \space \forall (i,j) \in \big\{0,...,m-1\} \times \big\{0,...,n-2\}$$ $$array[i][j] \leq array[i+1][j] \space \space \forall (i,j) \in \big\{0,...,m-2\} \times \big\{0,...,n-1\}$$

The algorithm needs to have a complexity of: $$\Theta (m+n)$$

My first idea was first to "walk" through the first column to check if it contains a number which is bigger than the number that I am looking for. If you try to find the number 5 in the following matrix you will realize that my thoughts do not work with this example.

$$\begin{pmatrix} 1 & 2 & 5 \\ 2 & 6 & 7 \\ 4 & 8 & 9 \end{pmatrix}$$

It would be great if someone could give a hint. Thank you very much!

Start looking in the top right corner of the matrix. Then repeat the following: if you have found $x$, return true; if the number you found is larger than $x$, move one entry to the left; if it is smaller, move one entry down.
If this would take you out of the bounds of the matrix, return false.
Formally, in order to give this a running time of $\Theta(n + m)$ rather than just $\mathcal O(n + m)$, you should compute $n + m$ in unary afterwards.
• My bad. $\ \ \$ May 26, 2016 at 14:56