LeeCode74 搜索二维矩阵

 先看下题目

看到这个题我第一时间想的是二分查找，只不过跟官方不同的是，我的是外层遍历，找到可能存在target的行，然后内层二分查找，判断具体有没有target这个数。我觉得我的想法也可以实现，只不过题目要求用高效的方法求解，遍历明显不太高效。

看看官方的程序

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()和binary_search()，之前也解释过了，再看看吧（10）STL算法之搜索（二）& 二分查找

还有upper_bound()的第四个参数运行的机制，上边链接里的源码里也有。参数四自定义规则里的参数一就是target，参数二是matrix外层的遍历，然后你可以在函数体内自定义比较规则。