Saturday, 25 February 2017

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