# Search a 2D Matrix – Leetcode Solution

In this post, we are going to solve the 74. Search a 2D Matrix problem of Leetcode. This problem 74. Search a 2D Matrix is a Leetcode medium level problem. Let’s see the code, 74. Search a 2D Matrix – Leetcode Solution.

Contents

## 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.

### Example 1 :

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

### Example 2 :

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

### Constraints

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 100`
• `-104 <= matrix[i][j], target <= 104`

Now, let’s see the code of 74. Search a 2D Matrix – Leetcode Solution.

# Search a 2D Matrix – Leetcode Solution

### 74. Search a 2D Matrix – Solution in Java

```class Solution {

public boolean bs(int[][] matrix,int row, int start, int end, int target){
while(start <= end){
int mid = start - ( start - end) / 2;
if(target == matrix[row][mid]) return true;
else if(target < matrix[row][mid]) end = mid-1;
else if(target > matrix[row][mid]) start = start + 1;
}
return false;
}
public boolean searchMatrix(int[][] matrix, int target) {

//finding potential row
int m = matrix.length-1;
int sRow = 0;
int eRow = matrix.length-1;
while(sRow <= eRow){
int mid = sRow - (sRow - eRow)/2;
if(target == matrix[mid] || target == matrix[mid][m]) return true;
else if(target > matrix[mid] && target < matrix[mid][m]){
return bs(matrix, mid, 0, m, target);
}
else if(target < matrix[mid]){
eRow = mid - 1;
}
else if(target > matrix[mid][m]){
sRow = mid + 1;
}
}

return false;
}

}```

### 74. Search a 2D Matrix– Solution in C++

```class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
int m = matrix.size();

if(n == 0 || m == 0)
return false;

int start = 0, end = m*n - 1;

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

int ind = matrix[mid/m][mid%m];
if (target == ind)
return true;

else if(target < ind)
end = mid - 1;
else

start = mid + 1;
}
return false;
}
};```

### 74. Search a 2D Matrix – Solution in Python

```class Solution:
def searchMatrix(self, matrix, target):
if not matrix or not matrix: return False
m, n = len(matrix), len(matrix)
beg, end = 0, m*n - 1
while beg < end:
mid = (beg + end)//2
if matrix[mid//m][mid%m] < target:
beg = mid + 1
else:
end = mid
return matrix[beg//m][beg%m] == target```

Note: This problem 74. Search a 2D Matrix is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.