# Search in a 2D Matrix (C++)

Question : You are given a 2D matrix of mxn ; your task is to find if the given number in the matrix exist or not .The matrix has the following properties :
1)Integers in each row are sorted from left to right :
2)The first integer of each row is greater than the last integer of the previous row.

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]],
target = 3
Output: true

Brute Solution :

To check the given element . if it exist in the matrix or not , we can simply iterate through the matrix and check all the elements if it is equal to given element or not . If we hit the element then return true else return false.
Pseudo Code :
for (i=0 to n-1)
for(i=0 to m-1)
if(matrix[i][j]==ele){return true}

Time complexity : O(nxm)
Space Complexity : O(1)

Optimal Solution :
For the optimal solution , we will be moving with two pointers . We will place our one pointer in the last element of first row and and other pointer in first element of first row . lets take i is our first pointer and j is our second pointer , so basically , i = 0 and j = matrix.size()-1 .
Now we will be iterating till our second pointer is equal to 0 i..e. j>=0 and first pointer is less than no of rows , so i will iterate from 0th row to last row , and j will iterate from last coloumn to first coloumn .
Basically , while(i<matrix.size() and j>=0) .

Once you start iterating first check , if you current element is equal to target , if yes then return true , else check if your current element is greater than target , if it is so then your target element actually lies to the left of you current element , so you have to do j– . In case when your current element is less than target , then your element actually greater than current element so it lies below your current row , so just go to the next row by doing i++ . Once you complete your loop and dont find your target element simply return false .

if(matrix[i][j]==target)
{
return true;
}
else if(matrix[i][j]>target)
{ j– ; }
else
{ i++; }

Code :
C++ :
Function to check if your target element is in the matrix or not :

bool searchMatrix(vector<vector<int>>& matrix, int target) {

``````    int i=0;
int j=matrix.size()-1;

while(i<matrix.size() and j>=0)
{
if(matrix[i][j]==target)
{
return true;
}
else if(matrix[i][j]>target)
{
j--;
}
else
{
i++;
}

}
return false;

}``````

Time complexity : O(log (nxm))
Space Complexity : O(1)