# Find element in 2D matrix where rows and columns are sorted

Elements of a matrix are given in sorted rows and columns. I want to find the element in an optimized way.

First, I will get the last element of a row, which will determine if a number can exist in the current row. If the number I want to search for is greater than the last row's element, there is no point is searching in that row.

#include <iostream>
#include <vector>

using std::vector;
using std::endl;
using std::cout;

int main()
{
vector <vector<int>> arr
{
{10,20,30},
{25,26,60},
{38,47,50}
};

int target = 47; // just test

int r, c;
r = 0;

bool found = false;

for (r = 0; r < arr.size(); r++)
{
c = arr[0].size() - 1;

while (arr[r][c] < target)//skip the row
{
r++;
}

while(arr[r][c] > target && arr[r][0] < target)
{
c--;

if (c < 0)
break;
}

if (arr[r][c] == target)
{
found = true;
break;
}
}

if(found)
cout << r << " " << c;
else
{
cout << "Not Found";
}

return 0;
}

//output : 2 1

• Why don't you just use 2 for loops ? – Denis Dec 25 '16 at 18:15
• @denis because I don't need to. Column index needs to change at different time than row change. – Pranit Kothari Dec 25 '16 at 18:16

## 1 Answer

You can modify the for loop to while. Running a for loop and within it while loops. Using a single while loop will do it, see the code below.

Also before checking this while loops check for the if that you are checking later on after while.

while (arr[r][c] < target)//skip the row
{
r++;
}

while(arr[r][c] > target && arr[r][0] < target)
{
c--;
if (c < 0)
break;
}


you should check for if search number is equal to this number in matrix before above while loops

if (arr[r][c] == target)
{
found = true;
break;
}


See below code.

//  n = the dimension matrix.
int i = 0, j = n-1;
while ( i < n && j >= 0 )
{
if ( arr[i][j] == x )
{
cout<<"\n Element Found at " << i << ", " << j;
break;
}
if ( arr[i][j] > x )
j--;
else //  if arr[i][j] < x
i++;
}
cout<<"\n Element not found";


Time Complexity: O(n)

This approach will work for (m * n) matrix as well not only for (n * n) matrix. Time Complexity in such case will be: O(m + n).