• 0

Search in partial sorted matrix
  • searching
  • sorting
  • matrix
  • row
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3629)

Suppose you are given a \( n \times n \) matrix which is partially sorted such that the biggest element in row i is smaller than the smallest element in row ( i + 1 ). How will you find an element in the matrix?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

We can find the element by modifying the binary search. Since the biggest element in row i is smaller than the smallest element in row i + 1 , as given, all the elements in row i will be less than all the elements in row i + 1 and greater than all the elements in row i - 1 . Thus we have to first find which row the element (we are looking for) belongs to. The algorithm works as :


  • Pick the \( (\frac{n}{2})^{th} \) row. Find the smallest and largest items in this row.
  • Compare the given element with these smallest and largest items.
  • If the given element is in between these smallest and largest items, the target lies in this row. Iterate through this row to search for it.
  • If the given element is less than the smallest element recurse the algorithm on the sub-matrix above \( (\frac{n}{2})^{th} \) row.
  • If the given element is greater than the largest element recurse the algorithm on the sub-matrix below \( (\frac{n}{2})^{th}\) row.

Time to find the row in which the element belongs to = \( O(logn) \).
Time to find the smallest and largest element in a row = \( O(n) \).
\( \therefore \) Overall time complexity = \( O(n) \).

You need to Sign In to post your solution.