# C Program to implement search Operation in Matrix

This question has been already appeared in the interviews of the following companies:-
OLA, MakeMyTrip, Oracle, One97, TinyOwl, Polycom, Visa, Directi, Inmobi, Groupon

Source: geeksforgeeks

In this question you have given a matrix of n*m order in which every row and column is sorted in increasing order and an element x. You have to find the element x in the given matrix. If the element is present in the matrix then print 1 otherwise print 0.

Note:- You have to find the element in O(m+n) Time Complexity

ALGORITHM

1. set:  element= element to be searched in the matrix
2. for i in range 1 to n   #n is the number of rows
3.      if  element>=matrix[i] and element<=matrix[i][m]
4.            for j in range 0 to m   #m is the number of columns
5.                  if element=matrix[i][j]
6.                       return True
7.                  EndIf
8.            EndFor
9.      EndIf
10. EndFor
11. return False
12. Exit

PROGRAM:

```#include <stdio.h>

class matrix_search{

private:
int matrix;
int n,m;
public:
void get_data();
void print();
bool search(int element);
};
void matrix_search::get_data()
{
int i,j,element;
printf("\nEnter the number of rows and columns of matrix: ");
scanf("%d%d",&n,&m);  /*n rows and m columns */
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf("%d",&matrix[i][j]);
}
}
}
void matrix_search::print()
{
int i,j;
printf("\nInput matrix is: \n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("%d  ",matrix[i][j]);
}
printf("\n");
}
}
bool matrix_search::search(int element)
{
int i,j;
for(i=0;i<n;i++)
{
if(element>=matrix[i] && element<=matrix[i][m-1] )
{
for(j=0;j<m;j++)
{
if(element==matrix[i][j])
{
return true;
}
}
}
}
return false;
}
int main()
{
matrix_search ms;
ms.get_data();
int element;
printf("\nEnter the element you want to search in the matrix: ");
scanf("%d",&element);
if(ms.search(element))
{
printf("\nElement is present in the matrix !");
}
else
{
printf("\nElement is not present in the marix !");
}
return 0;
}```

OUTPUT: