1
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @MartinArgerami Your matrix is invalid. Check the terms in my first post. $\endgroup$
    – peter87
    May 26, 2016 at 14:21
  • $\begingroup$ My bad. $\ \ \ $ $\endgroup$ May 26, 2016 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .