题目

个人解答：

题目中明确提出高效，此外数组是升序排列的，因此应该考虑二分查找。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size()-1;
        int i = 0,n =matrix[0].size()-1;
        if(target<matrix[0][0]||target>matrix[m][n])
            return false; 
        if(m==0)
        {
            for(int j=0;j<=n;j++)
            {
                if (target==matrix[i][j])
                    return true;
                else if (target<matrix[i][j])
                    return false;
            }
        }
        while(i<=m)
        {
            if(target>matrix[i][n])
                i++;
            else if(target<matrix[i][0])
                return false;
            else
            {
                for(int j=0;j<=n;j++)
                {
                    if (target==matrix[i][j])
                        return true;
                    else if (target<matrix[i][j])
                        return false;
                }
            }
        }
        return true;
    }
};

官方解答：

方法一：两次二分查找

思路：

由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>> matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
            return b < a[0];
        });
        if (row == matrix.begin()) {
            return false;
        }
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};

upper_bound(STL容器函数)

方法二：一次二分查找

思路：

若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。

代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int x = matrix[mid / n][mid % n];
            if (x < target) {
                low = mid + 1;
            } else if (x > target) {
                high = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};