How to find a number in a matrix efficiently?

[frankfjf]

Hi guys, was wondering if someone could help me with a homework problem.

The problem: The input is an N x N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.

Attempt at a solution: To be honest, I'm quite stumped. I know that the obvious solution is to check each element for the number, but that could be a O(N^2) complexity algorithm. I know that with a single loop one could traverse the matrix diagonally either starting from the top left and going toward the bottom right, or the other way around, but am not sure how to use this observation to come up with an O(N) complexity algorithm, assuming I'm off to a good start.

The professor has said that a pseudocode solution is fine.

 

[chiro]

Hi guys, was wondering if someone could help me with a homework problem.

The problem: The input is an N x N matrix of numbers that is already in memory. Each individual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.

Attempt at a solution: To be honest, I'm quite stumped. I know that the obvious solution is to check each element for the number, but that could be a O(N^2) complexity algorithm. I know that with a single loop one could traverse the matrix diagonally either starting from the top left and going toward the bottom right, or the other way around, but am not sure how to use this observation to come up with an O(N) complexity algorithm, assuming I'm off to a good start.

The professor has said that a pseudocode solution is fine.

Have you tried looking at the diagonal elements? What bounds can you expect from these elements given the restrictions that are placed on the matrix?

 

[frankfjf]

Only thing that comes to mind is that the top left element would have to be the smallest and the bottom right element would ahve to be the largest.

 

[rcgldr]

Only thing that comes to mind is that the top left element would have to be the smallest and the bottom right element would ahve to be the largest.

OK, assuming the number you're searching for is greather than the top left number and smaller than the bottom right number, what is the "ideal" element to compare next?

 

[frankfjf]

The one that's 1 down and 1 to the right of the current element, I'd imagine.

 

[rcgldr]

How about starting with a simpler case, if you had a known ascending array (a list, not a matrix) of numbers (each number in the list is greater than the preceding number) , what would be the quickest to see if a given number existed in the array of numbers?

 

[frankfjf]

Hm. I'd say seeing if it was between the smallest and largest numbers, assuming it wasn't one of those.

 

[rcgldr]

Another analogy then. A computer picks a random number between 1 and 1024, and you have to guess what the number is within so many tries. Each time you guess, the computer will tell you if the number is less than your guess, greater than your guess, or equal to your guess (you found the number). What strategy could you use to minimize the average number of guesses?