solution.md

# 搜索二维矩阵
<p>编写一个高效的算法来判断 <code>m x n</code> 矩阵中，是否存在一个目标值。该矩阵具有如下特性：</p><ul>	<li>每行中的整数从左到右按升序排列。</li>	<li>每行的第一个整数大于前一行的最后一个整数。</li></ul><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0074.Search%20a%202D%20Matrix/images/mat.jpg" style="width: 322px; height: 242px;" /><pre><strong>输入：</strong>matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3<strong><br />输出：</strong>true</pre><p><strong>示例 2：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0074.Search%20a%202D%20Matrix/images/mat2.jpg" style="width: 322px; height: 242px;" /><pre><strong>输入：</strong>matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13<strong><br />输出：</strong>false</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>m == matrix.length</code></li>	<li><code>n == matrix[i].length</code></li>	<li><code>1 <= m, n <= 100</code></li>	<li><code>-10<sup>4</sup> <= matrix[i][j], target <= 10<sup>4</sup></code></li></ul>
<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp
int main()
{
    Solution sol;
    int a = 3, b = 4;

    vector<vector<int>> matrix = vector<vector<int>>(a, vector<int>(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;
}
```

## 答案
```cpp
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &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
```cpp
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &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
```cpp
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &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
```cpp
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &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;
    }
};
```