# 74. Search a 2D Matrix

```74. Search a 2D Matrix
DescriptionHintsSubmissionsDiscussSolution
Pick One
Write an efficient algorithm that searches for a value in an m x n 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, 50]
]
target = 3
Output: true
Example 2:

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

## 解法一：

```public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
int row = searchMatrix_BS1_hepler(matrix,0,matrix.length-1,target);
return searchMatrix_BS2_helper(matrix,0,matrix[0].length-1,target,row);
}

public boolean searchMatrix_BS2_helper(int[][] matrix,int left,int right,int target,int row){
int mid = (right -left)/2 + left;
if (left>right) return false;
if (target == matrix[row][mid]) return true;
if (target>matrix[row][mid]) {
left = mid+1;
return searchMatrix_BS2_helper(matrix,left,right,target,row);
} else {
right = mid-1;
return searchMatrix_BS2_helper(matrix,left,right,target,row);
}
}

public int searchMatrix_BS1_hepler(int[][] matrix,int left,int right,int target){
int mid = (right -left)/2 + left;
if (target == matrix[mid][0]){
return mid;
}else if (target>matrix[mid][0]){
if (target <= matrix[mid][matrix[0].length-1]){
return mid;
} else {
left = mid+1;
return searchMatrix_BS1_hepler(matrix,left,right,target);
}
}else if (target<matrix[mid][0]){
if (target >=matrix[mid-1][0]){
return mid-1;
}else {
right = mid -1;
return searchMatrix_BS1_hepler(matrix,left,right,target);
}
}
return -1;
}```

## 解法二：

```public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
return searchMatrix_helper(matrix,target,0,matrix.length*matrix[0].length-1);
}

public boolean searchMatrix_helper(int[][] matrix, int target,int left,int right){
if (left > right ) return false;
int mid = (right -left)/2+left;
int row = mid/matrix[0].length;
int col = mid - matrix[0].length*row;
if (target == matrix[row][col]) return true;
if (target>matrix[row][col]) return searchMatrix_helper(matrix,target,mid+1,right);
else return searchMatrix_helper(matrix,target,left,mid-1);
}```

# 240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n 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:

Consider the following 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]
]```

Given target = `5`, return `true`.

Given target = `20`, return `false`.

## 解法一：

```    public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
return searchMatrix(matrix,target,0,matrix[0].length-1);
}

public boolean searchMatrix(int[][] matrix, int target,int row ,int col){
if (row>=matrix.length||col<0) return false;
if (matrix[row][col] == target) return true;

if (matrix[row][col] < target) {
return searchMatrix(matrix,target,row+1,col);
}else {
return searchMatrix(matrix,target ,row,col-1);
}
}```

## 解法二：

```    public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0||matrix[0].length==0) return false;
int row = 0,col = matrix[0].length-1;
while (row<matrix.length&&col>=0){
if (matrix[row][col]>target){
col--;
}else if (matrix[row][col]<target){
row++;
}else {
return true;
}
}
return false;
}```

0 条评论

## 相关文章

4146

### Leetcode 78 Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: The...

1996

### 3223: Tyvj 1729 文艺平衡树

3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1347  Sol...

4035

47810

791

2606

### 7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G，最小公倍数是...

4668

3698

### 写给开发者的机器学习指南（十）

An attempt at rank prediction for topselling books using text regression

953

### BZOJ4766: 文艺计算姬

Description "奋战三星期，造台计算机"。小W响应号召，花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺 术细胞。普通计算机能计算一个带...

3378