## [Leetcode]74. Search a 2D Matrix(C++)

### 题目描述

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.

### 例子

#### 例子 1

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

#### 例子 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`
• `-10^4 <= matrix[i][j], target <= 10^4`

### 解题思路

``````#include <vector>

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

int left = 0;
int right = m - 1;
while (left < right) {
int mid = (left + right) / 2 + 1;
if (matrix[mid][0] > target) {
right = mid - 1;
} else if (matrix[mid][0] < target) {
left = mid;
} else {
return true;
}
}

int row = left;
left = 0;
right = n - 1;
while (left < right) {
int mid = (left + right) / 2;
if (matrix[row][mid] > target) {
right = mid - 1;
} else if (matrix[row][mid] < target) {
left = mid + 1;
} else {
return true;
}
}

return matrix[row][left] == target;
}
};
``````
• 时间复杂度: `O(log max(m,n))`
• 空间复杂度: `O(1)`

GitHub 代码同步地址： 74.SearchA2DMatrix.cpp

Built with Hugo
Theme Stack designed by Jimmy