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

In Case of any queries, please revert back.

Here we can use a binary type search. As we eliminate a full row or column, the complexity is O(n)