# 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
```
### after
```c
int main()
{
Solution sol;
int a = 3, b = 4;
vector> matrix = vector>(a, vector(b)) = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
int target = 3;
bool res;
res = sol.searchMatrix(matrix, target);
cout << res;
return 0;
}
```
## 答案
```c
class Solution
{
public:
bool searchMatrix(vector> &matrix, int target)
{
if (matrix.size() == 0 || matrix[0].size() == 0 || target < matrix[0][0] || target > matrix[matrix.size() - 1][matrix[0].size() - 1])
return false;
int up = 0, down = matrix.size() - 1, left = 0, right = matrix[0].size() - 1;
while (up < down)
{
int mid = up + (down - up + 1) / 2;
if (matrix[mid][0] == target)
return true;
else if (matrix[mid][0] > target)
down = mid - 1;
else
up = mid + 1;
}
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (matrix[up][mid] == target)
return true;
else if (matrix[up][mid] > target)
right = mid - 1;
else
left = mid + 1;
}
if (matrix[up][left] == target)
return true;
return false;
}
};
```
## 选项
### A
```c
class Solution
{
public:
bool searchMatrix(vector> &matrix, int target)
{
if (matrix.size() == 0 || matrix[0].size() == 0)
return false;
decltype(matrix.size()) row_front = 0, c_front = 0, row_back = matrix.size(), c_back = matrix[0].size();
while (row_front < row_back)
{
auto k = row_front + (row_back - row_front) / 2;
if (matrix[k][0] == target)
{
return true;
}
else if (matrix[k][0] < target)
{
row_front = k + 1;
}
else if (matrix[k][0] > target)
{
row_back = k;
}
}
if (row_front == 0)
{
return false;
}
decltype(matrix.size()) target_line = row_front - 1;
while (c_front < c_back)
{
auto j = c_front + (c_back - c_front) / 2;
if (matrix[target_line][j] == target)
{
return true;
}
else if (matrix[target_line][j] < target)
{
c_front = j + 1;
}
else if (matrix[target_line][j] > target)
{
c_back = j;
}
}
return false;
}
};
```
### B
```c
class Solution
{
public:
bool searchMatrix(vector> &matrix, int target)
{
if (matrix.empty())
return false;
int m = matrix.size();
int n = matrix[0].size();
int left = 0;
int right = m * n - 1;
while (left <= right)
{
int middle = (left + right) / 2;
int middle_element = matrix[middle / n][middle % n];
if (middle_element == target)
return true;
else if (middle_element < target)
left = middle + 1;
else
right = middle - 1;
}
return false;
}
};
```
### C
```c
class Solution
{
public:
bool searchMatrix(vector> &matrix, int target)
{
if (matrix.empty())
return false;
int m = matrix.size();
int n = matrix[0].size();
int row = 0, col = n - 1;
while (row < m && col >= 0)
{
if (matrix[row][col] < target && col == n - 1)
row++;
else if (matrix[row][col] == target)
return true;
else
col--;
}
return false;
}
};
```