240. Search a two-dimensional matrix

Idea 1: binary search

Because a two-dimensional matrix is increasing from left to right in each row, and from top to bottom in each column. Meets the criteria for binary search. We can search for the target value from the first row, and if we can’t find it, we can search for the next row to find the number of rows traversing the entire matrix.

// Binary search
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    // You need a reference here, otherwise it will time out
        for(auto &nums : matrix)
        {
            auto it = lower_bound(nums.begin(), nums.end(), target);
            if(it ! = nums.end() && *it == target)
                return true;
        }
        return false; }};Copy the code

The lower_bound() function: The lower_bound() function is used to find the first element in the specified range that is not less than the target value. That is, when you use this function to find a target value within a specified range, you may not end up finding elements equal to the target value, but may end up finding elements larger than the target value. The return value is an iterator.

Monotonic scanning O(M + N)

Enumerating from the top right corner of the entire matrix, assuming the current enumeration is x:

• If x is equal to target, we found the target value and return true;
• If x is less than target, then everything to the left of x must be less than target, so we can just exclude the entire current row;
• If x is greater than target, then everything below x must be greater than target, so we can exclude the entire current column.

The bosses say quite good, direct link II | search two-dimensional matrix from the upper right corner of the monotonicity scanning | code is concise and easy to understand c + + / Java version – search 】 the two-dimensional matrix II – force buckle (LeetCode) (leetcode-cn.com)