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?
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 :
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) \). |