Search in the Matrix

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

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

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 />