This question has been already appeared in the interviews of the following companies:-

In this question you have given a

**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][0] 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

2. for i in range 1 to n #n is the number of rows

3. if element>=matrix[i][0] 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[100][100]; 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][0] && 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:**

EmoticonEmoticon