Question

You are asked to write an efficient algorithm to search a given key within a given 2D array, where every row and column is sorted in an ascending order. For example consider a 2D arrary. Every row and column is sorted. You are searching the 2D array for key 36.  

3 7 11 23 45

5 9 13 25 50

7 14 15 30 55

10 18 22 34 62

16 24 29 38 88

Present pseudocode of an efficient algorithm for the search described above . Your input array size is n x n.

Answer 1

The algorithm/pseudocode is given as:

Let x = element we’re trying to search for in the matrix, and e = current element we’re processing in the array.

1) Start with top right element.
2) Loop: compare this element e with x
…i) if e = x, then return position of e, since we found x in the given matrix.
…ii) if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
…iii) if e < x then move below to check elements greater than e (if out of bound of matrix, then break and return false)
3) repeat the i), ii) and iii) until you find the element or return false

Time Complexity: O(n)