Searching in 2D sorted matrix.

Q. Write an efficient algorithm that searches for a value in an n x m table (two- dimensional array). This table is sorted along the rows and columns, that is

Table[i][j] < Table[i][j + 1]

Table[i][j] < Table[i + 1][j]

Answer:  Diagonal Step-wise Linear Search:

We can start this either from Top-Right element or from Bottom-Left element and then move up-right or down-left. In this question we will tackle this starting from the Top-Rightelement. (Other one is similar and is left as an exercise for the reader ). Here are the sudo steps that will be followed by the code.

1. Starting :Start from the top right element of the given 2-D matrix
2. Loop : compare the element say M(which you r looking for) with x(current element in the array)
   
   1. If they are equal then return its position you have found the element .
   2. M > x then move down for further searching (if out of bound of matrix then break return false)
   3. M < x then move left for further searching (if out of bound of matrix then break return false)
3. repeat the i), ii) and iii) till you find element or returned false.

bool stepWise(int mat[][N_MAX], int N, int target,
              int &row;, int &col;) {
  if (target < mat[0][0] || target > mat[N-1][N-1]) return false;
  row = 0;
  col = N-1;
  while (row < = N-1 && col > = 0) {
    if (mat[row][col] < target)
      row++;
    else if (mat[row][col] > target)
      col--;
    else
      return true;
  }
  return false; 

}