## Algorithm

Problem Name: 240. Search a 2D Matrix II

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 in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1:

```Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
```

Example 2:

```Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false
```

Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= n, m <= 300`
• `-109 <= matrix[i][j] <= 109`
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• `-109 <= target <= 10`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
bool search(int** matrix, int top, int left, int bottom, int right, int target) {
int row, col;
int i;
​
if (target  <  matrix[top][left] ||
target > matrix[bottom][right]) return false;
​
if (top == bottom) {
// can use binary search
for (i = left; i  < = right; i ++) {
if (matrix[top][i] == target) return true;
}
return false;
}
if (left == right) {
// can use binary search
for (i = top; i  < = bottom; i ++) {
if (matrix[i][left] == target) return true;
}
return false;
}
​
row = top + (bottom - top) / 2;
col = left + (right - left) / 2;
if (target == matrix[row][col]) return true;
if (target  <   matrix[row][col]) return (search(matrix, top, left, row, right, target) ||
search(matrix, row + 1, left, bottom, col - 1, target));
return (search(matrix, row + 1, left, bottom, right, target) ||
search(matrix, top, col + 1, row, right, target));
}
​
bool searchMatrix(int** matrix, int matrixRowSize, int matrixColSize, int target) {
#if 0  // 100+ ms
return search(matrix, 0, 0, matrixRowSize - 1, matrixColSize - 1, target);
#else  // 40+ ms
int r = 0;
int c = matrixColSize - 1;
while (r  < = matrixRowSize - 1 &&
c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] < target) r ++;
else c --;
}
return false;
#endif
}
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output

cmd
true

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty() || matrix[0].empty()) return false;
int lo = BS(matrix, 0, target), hi = BS(matrix, matrix[0].size() - 1, target);
for(int i = min(lo, hi); i <= max(lo, hi); i++){
auto it = lower_bound(matrix[i].begin(), matrix[i].end(), target);
if(it != matrix[i].end() && *it == target) return true;
}
return false;
}

int BS(vector < vector<int>>& matrix, int col, int target){
int lo = 0, hi = matrix.size() - 1, mid = lo + (hi - lo) / 2;
while(lo  < = hi>{
if(matrix[mid][col] > target) hi = mid - 1;
else lo = mid + 1;
mid = lo + (hi - lo) / 2;
}
return max(0, hi);
}
};
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output

cmd
true

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int rowIdx = rows - 1;
int colIdx = 0;
while (rowIdx >= 0 && colIdx  <  cols) {
if (matrix[rowIdx][colIdx] > target) {
rowIdx--;
} else if (matrix[rowIdx][colIdx] < target) {
colIdx++;
} else {
return true;
}
}
return false;
}
}
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20

Output

cmd
false

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const searchMatrix = function(matrix, target) {
if (matrix == null || matrix.length == 0) {
return false;
}

const length = matrix.length;
for (let i = 0; i  <  length; i++) {
const row = matrix.shift();
let left = 0,
right = row.length - 1;

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

if (row[mid] == target) {
return true;
} else if (row[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}

return false;
};
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20

Output

cmd
false

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def searchMatrix(self, matrix, target):
return any(target in row for row in matrix)
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output

cmd
true

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0240_SearchA2DMatrixII
{
public bool SearchMatrix(int[,] matrix, int target)
{
var n = matrix.GetLength(0);
var i = 0;
var m = matrix.GetLength(1) - 1;

while (i  <  n && m >= 0)
{
var cmp = matrix[i, m].CompareTo(target);
if (cmp == 0) return true;
else if (cmp > 0) m--;
else i++;
}
return false;
}
}
}
``````
Copy The Code &

Input

cmd
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

Output

cmd
true