Search in a matrix

PROBLEM :

Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . The task is to find whether element x is present in the matrix or not.

Expected Time Complexity : O(m + n)

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines.
First line of each test case consist of two space separated integers N and M, denoting the number of element in a row and column respectively.
Second line of each test case consists of N*M space separated integers denoting the elements in the matrix in row major order.
Third line of each test case contains a single integer x, the element to be searched.
Output:

Corresponding to each test case, print in a new line, 1 if the element x is present in the matrix, otherwise simply print 0.

Constraints:
1<=T<=200
1<=N,M<=30

Example:

Input:
2
3 3
3 30 38 44 52 54 57 60 69
62
1 6
18 21 27 38 55 67
55

Output:
0
1

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#define MAX 30
int Search_in_matrix(int [MAX][MAX],int ,int ,int ) ;
int main()
 {
int t,row,col,i,j,k;
int mat[MAX][MAX] ;
cin>>t ;
while(t--)
{
   cin>>row>>col ;
 
   for(i=0;i<row;i++)
       for(j=0;j<col;j++)
           cin>>mat[i][j] ;
   cin>>k ;        
   cout<<Search_in_matrix(mat,row,col,k) ;
   cout<<endl ;
}
return 0;
}

int Search_in_matrix(int mat[MAX][MAX],int row,int col,int k)
{
    int i,j ;
 
    for(i=0;i<row;i++)
        for(j=col-1;j>=0;j--)
        {
            if(mat[i][j]==k)
                return 1 ;
            else if(mat[i][j]<k)
                break ;
        }
    return 0 ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :( O(n) solution)
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#define MAX 30
int Search_in_matrix(int [MAX][MAX],int ,int ,int ) ;
int main()
 {
int t,row,col,i,j,k;
int mat[MAX][MAX] ;
cin>>t ;
while(t--)
{
   cin>>row>>col ;
 
   for(i=0;i<row;i++)
       for(j=0;j<col;j++)
           cin>>mat[i][j] ;
   cin>>k ;        
   cout<<Search_in_matrix(mat,row,col,k) ;
   cout<<endl ;
}
return 0;
}

int Search_in_matrix(int mat[MAX][MAX],int row,int col,int k)
{
    int i,j ;
    i=0 ;
    j=col-1 ;
 
    while(i<row&&j>=0)
    {
        if(mat[i][j]==k)
            return 1 ;
        else if(mat[i][j]<k)
        {
            i++ ;
            j=col-1 ;
        }
        else if(j==0)
        {
            i++ ;
            j=col-1 ;
        }
        else
            j-- ;
    }
    return 0 ;
}

---------------------------------------------------------------------------------