### Search in partial sorted matrix searching sorting matrix row    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (2922)

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: 5 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)$$.