# Search A 2D Matrix Problem Solution

Search A 2D Matrix Problem: Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `matrix`. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• 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```

## Problem Solution In Python

``````def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
if len(matrix) == 0 or len(matrix[0]) == 0:
return False

row = []
# store the row with great or equal value to the target
for record in matrix:
if record[-1] >= target:
row = record
break

# iterate through the row until you find the target
for element in row[::-1]:
if element == target:
return True

return False
``````

## Problem Solution In Java

``````class Solution {
public boolean searchMatrix(int[][] matrix, int target) {

//corner case
if(matrix == null || matrix.length == 0) return false;
if(matrix[0] == null || matrix[0].length == 0) return false;

int r = matrix.length;
int c = matrix[0].length;

int left = 0;
int right = r * c - 1;

while(left <= right){
int mid = left + (right - left)/2;

int value = matrix[mid / c][mid % c];

if(value == target){
return true;
}
else if(value < target)

left = mid + 1;
else
right = mid -1;
}
return false;
}
}
``````

## Problem Solution In C++

``````class Solution {
public:
bool searchMatrix(vector <vector<int> >& matrix, int target) {
int row = matrix.size(), col = matrix[0].size();
int left = 0, right = row * col - 1;
while (left <= right)
{
int mid = left +(right - left)/2;
int r = mid / col, c = mid % col;
if (matrix[r][c]==target) return true;
if (matrix[r][c] < target)
left = mid +1;
else
right = mid -1;
}
return false;
}
};
``````

## Problem Solution In C

``````bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
int totalRow=matrixSize;
if(totalRow==0 || *matrixColSize==0)
{
return false;
}

int start=0;
int end=matrixSize*(*matrixColSize)-1;
int row=0;

int col= 0;

int mid=0;

while(start<=end)
{
mid=(start+end)/2;

row=mid/(*matrixColSize);

col=mid%(*matrixColSize);

if(matrix[row][col]==target)
{
return true;
}

else if(matrix[row][col]>target)
{
end=mid-1;
}

else
{
start=mid+1;
}
}

return false;
}
``````