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外層的周遊，然後你可以在函數體内自定義比較規則。