Design an algorithm to search a key in a two dimensional matrix (N*M) illustrate

Question

Design an algorithm to search a key in a two dimensional matrix (N*M) illustrated as follows. The matrix has the property that the numbers in column are sorted in decreasing order, while the numbers in rows are sorted in increasing order. Please design and write a pseudo code to find a key in the matrix with linear efficiency. The O(N) should be no more than N + M, where N is the size for rows and M is the size for columns. Discuss the efficiency of you algorithm (O(N)) and illustrate your algorithm by searching number 71. A 5*8 matrix when N=5, M=8 in this case.

Explanation / Answer

The algorithm is as follows:

1. We will start the search for given number n from [0,0] position (first 0 denotes the row num and second 0 denotes the column number)
2. If n > M[0,0] then we will move to next column and if n < M[0,0] then we will move to the next row.
3. So we will be either moving forward or moving downward. And forward movement can not go beyond N and downward
   movement can not go beyond N.
4. In the worst case we need to N + M comparisons , otherwise we will always get the number less than N + M comparisons.
          
For 71

our comparisons (values compared) will go as follows: 10, 20, 30, 40,50,60,70,80,79,77,75,73

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.