Determine element x in an array where each row and column is in ascending order?

Question

Give an n^2 array of elements such that each row is in ascending order and each column is in ascending order, devise an O(n) algorithm to determine if a given element x in the array.

You may assume all elements in the n^2 array are distinct?

Answer 1

Try the following algo which I found on http://www.geeksforgeeks.org/
1) Start with top right element
2) Loop: compare this element e with x
....i) if they are equal then return its position
…ii) e < x then move it to down (if out of bound of matrix then break return false)
....iii) e > x then move it to left (if out of bound of matrix then break return false)
3) repeat the i), ii) and iii) till you find element or returned false

int search(int **arr, int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element

   while ( i < n && j >= 0 )
   {
      if ( arr[i][j] == x )
      {
         printf("\n Found at %d, %d", i, j);
         return 1;
      }
      if ( arr[i][j] > x )
        j--;
      else //  if arr[i][j] < x
        i++;
   }

   printf("\n Element not found");
   return 0;  
}