74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

• new solution update 2022.02.13

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), l = 0, r = n - 1;
        while(l < r) {
            int m = l + (r-l)/2;
            if(matrix[m][0] == target) return true;
            else if(matrix[m][0] > target) r = m - 1;
            else if(matrix[m].back() < target) {
                l = m+1;
            }
            else if(l == m) break;
            else l = m;
        }
        auto it = lower_bound(matrix[l].begin(), matrix[l].end(), target);
        return it != matrix[l].end() and *it == target;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(auto& vec : matrix) {
            if(vec.back() < target) continue;
            return *lower_bound(begin(vec), end(vec), target) == target;
        }
        return false;
    }
};