题目：搜索二维矩阵

解法一：

把二维矩阵转入一维数组，再对这个数组进行二分查找

空间、时间复杂度都为O(M * N)

 1bool searchMatrix(vector<vector<int>>& matrix, int target)
 2{
 3    std::vector<int> vec;
 4    vec.reserve(matrix.size() * matrix[0].size());
 5    for(auto row : matrix)
 6    {
 7        for(auto element : row)
 8        {
 9            vec.push_back(element);
10        }
11    }
12    return std::binary_search(vec.begin(), vec.end(), target);
13}

<font style="background-color:#FBDE28;">解法二：</font>

核心公式：a[ i ]=matrix [ i / n ][ i mod n ]

实际上并不需要再开辟一个M*N的空间用于存储二维矩阵，可以直接根据一维数组下标与行列的关系找到对应元素

 1bool searchMatrix(vector<vector<int>>& matrix, int target)
 2{
 3    int rows = matrix.size(), cols = matrix[0].size();
 4    int left = 0, right = rows * cols;
 5    while(left < right)
 6    {
 7        int mid = left + (right - left) / 2;
 8        int x = matrix[mid / cols][mid % cols];
 9        if(target == x)
10            return true;
11        else if(x < target)
12            left = mid + 1;
13        else if(target < x)
14            right = mid;
15    }
16    return false;
17}