**source:**https://leetcode.com/problems/search-a-2d-matrix**C/C++**

**Solution to LeetCode**problem

**74**.

**Search a 2D Matrix**.

## Problem

You are given an `m x n`

integer matrix `matrix`

with the following two properties:

- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.

Given an integer `target`

, return * true if target is in matrix or false otherwise*.

You must write a solution in `O(log(m * n))`

time complexity.

## Examples

**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

Two binary searchs (nested or not). First, we find the row where the number should be located. Then, with a second binary search we find the position of the number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool inRow = false;
int l = 0;
int h = matrix.size() - 1;
int m;
while (l<=h) {
m = (l + h) / 2;
if (matrix[m][0] == target || matrix[m][matrix[m].size() - 1] == target)
return true;
if (matrix[m][0] < target && matrix[m][matrix[m].size() - 1] > target) {
inRow = true;
break;
}
if (matrix[m][0] > target)
h = m - 1;
if (matrix[m][matrix[m].size() - 1] < target)
l = m + 1;
}
if (inRow) {
l = 0;
h = matrix[m].size() - 1;
int m2;
while (l <= h) {
m2 = (l + h) / 2;
if (matrix[m][m2] == target)
return true;
if (matrix[m][m2] > target)
h = m2 - 1;
if (matrix[m][m2] < target)
l = m2 + 1;
}
}
return false;
}
};