We a Matrix where every ROW and COL are sorted something like the below:

1 4 5 6

2 5 7 9

3 6 8 10

**give a number, you need to search whether it is there in the Matrix or not.**

__Problem__:

**Solution:**The below solution's complexity is O(m+n) where m - ROW, n - COL

<br />#include<iostream><br />using namespace std;<br />#define ROW 4<br />#define COL 5<br /><br />int Matrix[ROW][COL] = {<br /> { 1, 3, 5, 7, 9},<br /> { 2, 4, 6, 8, 10},<br /> {11,13,15,17, 19},<br /> {20,40,60,80,100}<br />};<br />bool isValid(int row, int col)<br />{<br /> if(row >= 0 && col < COL)<br /> {<br /> return true;<br /> }<br /> return false;<br />}<br />int main()<br />{<br /> int i = ROW-1;<br /> int j = 0; // Zeroth Column<br /> int searchItem = 0;<br /><br /> cout<<"enter the number to be searched: ";<br /> cin >> searchItem;<br /><br /> while(isValid(i, j))<br /> {<br /> if(Matrix[i][j]== searchItem)<br /> {<br /> cout<<"Item found @ ("<< i<<","<< j << ") :"<< searchItem<< endl;<br /> return 0;<br /> }<br /> else if (Matrix[i][j] > searchItem)<br /> {<br /> //go up, which means reduce the row<br /> i--;<br /> }<br /> else<br /> {<br /> // itea is lesser than the index, go right<br /> j++;<br /> }<br /> }<br /> cout<<"Item not found :("<< endl;<br /> return 0;<br />}<br />

## No comments:

## Post a Comment