Play this article

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

.

### Did you find this article valuable?

Support **Nhut Nguyen** by becoming a sponsor. Any amount is appreciated!