Elegant C++ solution using STL, 3 lines, 12ms.

  • 1

    At first, use "lower_bound" to find a row(matrix[i]) in matrix that:

    matrix[i-1].back() < target <= matrix[i].back()

    Then, use "binary_search" to search "target" in this row(matrix[i]).

    The AC code demonstrates the power and elegance of STL:

    class Solution {
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            auto compfunc = [](const vector<int> &v, const int x) {return v.back() < x;};
            auto itr = lower_bound(matrix.begin(), matrix.end(), target, compfunc);
            return itr != matrix.end() && binary_search(itr->begin(), itr->end(), target);

    You can get more information about "lower_bound" and "binary_search" at:


Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.