·

# 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)`.