Program 15TH in C++ (VERSION 2)

PROBLEM STATEMENT :

Matrix with rows and column sorted. Find a particular element.

NOTE:

Works for arrays where the last element of previous row in 2d matrix is less than first element of next row with time complexity l0g m +log n

SOLUTION :

#include <iostream.h>

#include <cstdio>

using namespace std;

void find(int arr[][4], int m, int n, int target, int &row, int &col)

{

int a1d[16];

int first;

int last;

for(int x=0; x<16; x++)

{

a1d[x]=arr[x/m][x%n];

}

first=0;

last=15;

while(first>=0 && last<16 && first <= last)

{

int mid = (first+last)/2;

if(a1d[mid]==target)

{

row=mid/m;

col=mid%n;

return;

}

else if(a1d[mid] > target)

{

last=mid-1;

}

else

{

first=mid+1;

}

}

}

int main()

{

int a2d[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};

int val;

cout<<"\n\nEnter the element you want to find : ";

cin>>val;

int row = -1;

int col = -1;

find(a2d,4,4,val,row,col);

if(row !=-1 && col !=-1)

{

cout<<"\n\nElement is at row : "<<row <<" and column : "<<col<<endl;

}

else

{

cout<<"\n\nElement not present in the array\n\n";

}

}