Share my C++ 6 lines O(log m + log n) codes (using STL function lower_bound)


  • 3

    The basic idea of the program is as follows:

    (Step 1) Use lower_bound (with predication) to find the correct row.

    Time complexity: O(log m)

    (Step 2) Use binary_search (without predication) to check the existence of the target element.

    Time complexity: O(log n)

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            bool ret = false;
            if ((!matrix.empty()) && (!matrix.front().empty())) {
                auto pred = [](vector<int> & vval, int ival){return vval.back() < ival;};
                auto it = lower_bound(matrix.begin(), matrix.end(), target, pred);
                if (it != matrix.end()) {
                    ret = binary_search(it->begin(), it->end(), target);
                }
            }
            return ret;
        }
    };

Log in to reply
 

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