Problem statement

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints

• m == matrix.length.
• n == matrix[i].length.
• 1 <= m, n <= 100.
• -10^4 <= matrix[i][j], target <= 10^4.

Solution: Binary search on the row of interest

All rows are sorted, so you can perform a binary search on one of them. The only thing is choosing which row to do the searching.

Code

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int i = matrix.size() - 1;
    while (i >= 0 && target < matrix[i][0]) {
        i--;
    }
    if (i >= 0) {
        return binary_search(matrix[i].begin(), matrix[i].end(), target);
    }
    return false;
}
int main() {
    vector<vector<int>> matrix{{1,3,5,7},{10,11,16,20},{23,30,34,60}};
    cout << searchMatrix(matrix, 3) << endl;
    cout << searchMatrix(matrix, 13) << endl;
}

Output:
1
0

Complexity:

• Runtime: O(m + logn), where m = matrix.length, n = matrix[i].length.
• Extra space: O(1).