Program to search element in Matrix in C
To search in 2d Matrix two method one is brute force method compare with each element but time complexity in O(m*n).
But in optimal method using binary search complexity is O(log(m*n)) which is less than brute force method.
Method1:brute force method to search element in 2d Matrix.
#include <stdio.h>
int main() {
int a[3][2]={{1,2},{3,4},{5,6}};
int item=3;
int i,j;
int n=3;
int m=2;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]==item)
{
printf("element found at a[%d][%d]",i,j);
break;
}
}
}
}
Complexity of brute force is O(m*n) because two loop is used in this method.
Method 2:optimal solution to search element in 2d Matrix.(using binary search)
#include <stdio.h>
int main() {
int a[3][2]={{1,2},{3,4},{5,6}};
int item=6;
int i,j;
int n=3;
int m=2;
int low=0;
int high=((n*m)-1);
int row;
int col;
int mid;
while(low<=high)
{
mid=(low+high)/2;
row=mid/m;
col=mid%m;
if(a[row][col]==item)
{
printf("element found at a [%d][%d]",row,col);
break;
}
else if(a[row][col]<item)
low=mid+1;
else
high=mid-1;
}
if(low>high)
printf("element not found");
}
Complexity of optimal search in 2d Matrix is
O(log(m*n)). which is less than brute force method.
0 Comments