# 74. Search a 2D Matrix

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/05/mat.jpg)

<pre><code><strong>Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
</strong><strong>Output: true
</strong></code></pre>

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/10/05/mat2.jpg)

<pre><code><strong>Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
</strong><strong>Output: false
</strong></code></pre>

&#x20;

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 100`
* `-104 <= matrix[i][j], target <= 104`

## Intuition

```
Approach:

Treating the entire 2D array as one
Now, using mid/n, mid%n 
Trick acces the elemets
```

### Links

<https://leetcode.com/problems/search-a-2d-matrix/description/>

### Video Links

<https://www.youtube.com/watch?v=JXU4Akft7yk&ab_channel=takeUforward>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int low=0, high=matrix.size()*(matrix[0].size())-1;
        int n=matrix[0].size();

        while(low<=high){
            int mid=low+(high-low)/2;

            if(matrix[mid/n][mid%n]==target)
                return true;
            else if(matrix[mid/n][mid%n]<target)
                low=mid+1;
            else
                high=mid-1;
        }

        return false;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###