# Search in a matrix

QUESTION

Given an n x m matrix, where every row and column is sorted in increasing order, and a number x . \n\nThe task is to find whether element x is present in the matrix or not.\n\nExpected Time Complexity : O(m + n)\n\nInput:\nThe 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.\nFirst 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.\nSecond line of each test case consists of N*M space separated integers denoting the elements in the matrix in row major order.\nThird line of each test case contains a single integer x, the element to be searched.\n\nOutput:\n\nCorresponding to each test case, print in a new line, 1 if the element x is present in the matrix, otherwise simply print 0.\n\nConstraints:\n1<=T<=200\n1<=N,M<=30

``````#include <stdio.h>
int main()
{
int n,i,j,f,r,c,d,a,b;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&r,&c);
d=r*c;
for(j=1;j<=d;j++)
scanf("%d ",&a[j]);
scanf("%d",&f);
for(j=1;j<=d;j++)
{
if(f==a[j])
{
b[i]=1;
break;
}
else
b[i]=0;
}
}
for(i=1;i<=n;i++)
printf("%d\n",b[i]);
return 0;
}``````  