Data Structures problem

  • Thread starter frankfjf
  • Start date
  • #1
168
0

Main Question or Discussion Point

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.
 

Answers and Replies

  • #2
chiro
Science Advisor
4,790
131
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?
 
  • #3
168
0
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.
 
  • #4
rcgldr
Homework Helper
8,682
518
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?
 
  • #5
168
0
The one that's 1 down and 1 to the right of the current element, I'd imagine.
 
  • #6
rcgldr
Homework Helper
8,682
518
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?
 
Last edited:
  • #7
168
0
Hm. I'd say seeing if it was between the smallest and largest numbers, assuming it wasn't one of those.
 
  • #8
rcgldr
Homework Helper
8,682
518
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?
 

Related Threads on Data Structures problem

  • Last Post
Replies
9
Views
905
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
4K
Replies
4
Views
4K
  • Last Post
Replies
8
Views
2K
Replies
11
Views
1K
Replies
2
Views
581
Replies
5
Views
2K
  • Last Post
Replies
1
Views
689
Replies
1
Views
2K
Top