Need help writing an algorithm with O(N) that searches to see if a number X is in an N x N matrix?

Question

With the input N by N matrix of numbers that is already in memory.

Each row is increasing left to right
Each column is inceasing top to bottom

I drew an example 5 x 5 matrix to try and help

0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8

But I'm still having a hard time seeing how I can look through the matrix[ ][ ] and keep my algoritm O(N).

This is all in Java. Pseudocode would help too!

Thank you!

Answer 1

if by O(N), you're basing it on an M by M matrix?



it'd be as simple as



start at 0

row = 0

column = 0

maxrox = 50

maxcolumn = 50

while(row < maxrow)

{

while(column < maxcolumn)

{

if(lookingFor == array[row][column])

return true;

column++;

}

row++;

}

Answer 2

Well, I just see the best approach to this one being the fact that you have a very clearly defined array, and you don't need to know how many times the number shows up right? Just a yes/no answer at the end. So your array has the numbers 0 to 8, with all the numbers in between. So you just need to do two tests on the number that you are given as an input.

Is the number >= 0?

Is the number <= max?

If the answer to both is true, return true.

If the answer to either is false, reture flase.

Job done, and you are within O(n) time, you actually have a static O(two if) time, which is better than O(n) by a long shot. It really depends on who much cleverness is allowed, and the exact wording of the question on this one.



:)

Answer 3

Do you have any previous techniques concerning the trend of the values of the table or are they only assumed to be random? If that is random, basically use a brute rigidity set of rules. i'm assuming which you have formed an (n x m) matrix A from the table. I purely rather know Stata, so right this is code which you may adapt to regardless of application you're making use of. i'm assuming there are probably varied situations interior the table the place you ought to hit upon a tournament. interior of reach x = [your variety] * intiating case counter at 0 interior of reach ok = 0 * first looping over rows, then over cols for r = one million(one million)n { for c = one million(one million)m { * figuring out regardless of if we've got here across a tournament interior of reach v = A[`r',`c'] * in that case, upload to the case counter and checklist row and column place if `v'==`x' { interior of reach ok = `ok'+one million interior of reach row`ok' = `r' interior of reach col`ok' = `ok' } // final if assertion } // final column loop } // final row loop * Now reporting if `ok' == 0 { disp "No tournament" } else { forvalues a = one million(one million)`ok' { * reporting tournament variety and linked row and column positions disp "tournament variety " `a': disp " row = " `row `a' ' disp "and column = " `col `a' ' } // final tournament loop } final else statment *** end If x is s unique interior the table, you may choose to function a harm assertion once you hit upon it and overlook concerning the ok counter.