#### Approach #1 Brute Force [Accepted]

**Algorithm**

Traverse the array comparing every element with the given target. Return `true`

if the target was found return `false`

after the completion of an iteration meaning that a target is not in a given array.

**C++**

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(int row = 0; row<matrix.size(); row++) {
for(int col = 0; col<matrix[row].size(); col++) {
if(matrix[row][col] == target) {
return true;
}
}
}
return false;
}
```

**Complexity Analysis**

- Time complexity : $$O(mn)$$.

Because each of these nested loops executes `m`

and `n`

times respectively, the total time complexity is $$O(mn)$$, where m represents `rows`

and n `columns`

.

- Space complexity : $$O(1)$$.

#### Approach #2 Binary Search [Accepted]

**Algorithm**

The fact that every row of a given array is `sorted`

make it possible to apply `binary search`

for every row to search for the target value. Keep dividing a row in halves until a finding of the target value.

**C++**

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for(int row = 0; row<matrix.size(); row++) {
int l = 0, r = (int)matrix[row].size()-1;
while(l<=r) {
int middle = l + (r - l)/2;
if(matrix[row][middle] == target) {
return true;
} else if(matrix[row][middle] < target) {
l = middle + 1;
} else {
r = middle - 1;
}
}
}
return false;
}
```

**Complexity Analysis**

- Time complexity : $$O(mlogn)$$.

Iteration through rows in a given array takes `m`

time where `binary search`

on a row takes `logn`

time, the total time complexity is $$O(mlogn)$$, where m represents `rows`

and n `columns`

.

- Space complexity : $$O(1)$$.

#### Approach #2 Pointer [Accepted]

**Algorithm**

The hint for this approach is the fact that

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

Lets start the pointer at last column of the first row meaning that `all numbers below current number are greater than current number and all numbers left to current number are less than current number`

. Comparing current number with target number it can be decided in which direction to move the pointer. If current number is equal to a target number this means that target value was found stop the pointer. If current number is less than target number then consider numbers below so move the pointer to next `row`

; otherwise, if current number is greater than current number consider all numbers on the left in the same `row`

by moving the pointer to the left.

**C++**

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.size() == 0) {
return false;
}
int m = (int)matrix.size();
int n = (int)matrix[0].size();
int row = 0, col = n-1;
while(row<m && col>=0) {
if(matrix[row][col] == target) {
return true;
} else if(matrix[row][col]>target) {
col--;
} else {
row++;
}
}
return false;
}
```

**Complexity Analysis**

- Time complexity : $$O(m+n)$$.

Iteration through rows in a given array takes `m`

time and iteration through columns takes `n`

time. The fact that the pointer can only move down or left makes the total time complexity $$O(m+n)$$, where m represents `rows`

and n `columns`

.

- Space complexity : $$O(1)$$.