A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array?

Problem:

A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array?

Solution:

The solution described below is O(n) solution.

Start from top right element,

• If the element is equal to element we are searching for return the element.
• If the element is greater than the element we are searching for, then all the element in the column below can be discard. Move to element left of current element. Repeat the steps with new current element.
• If the element is less than the element we are searching for, then all the element in the row of current element can be discard. Move to element below of current element. Repeat the steps with new current element.

Pseudo code:

Pair find(int[][] a,int top, int bottom, int left, int right,int key) 

       if (top > bottom || left > right) return null;

       int current = a[top][right]

       if (current == key)

              return Pair(top,right)

       else if (current < key)

              return find(a,top+1,bottom,left,right,key)

       else

              return find(a,top,bottom,left,right-1,key)

 

Call find(0,n-1,0,m-1,key) to search for key.