question

Given a 2D matrix sorted in increasing order from left-to-right and top-to-bottom, devise an algorithm to search for a target number.

If the target is larger/smaller than an element at the end of a row/column, what can you say about where the target is.

This solution usees recursion to elininate one line/column at every call. If the matrix NxM then the algorithm will run in O(N + M).

Thoughts or alternate solution? Let us know in the comments below!

```
```

int **searchMatrix**(int target, int[][] matrix, i, j)

int t = matrix[i][j];

**if** (target == t)

**return** t;

**else if** (target > t)

**return searchMatrix**(target, matrix, i + 1, j);

**else**

**return searchMatrix**(target, matrix, i, j - 1);

**searchMatrix**(target, matrix, 0, M) // Initially called at 'upper right' corner of matrix. M is number of columns.

Thoughts or alternate solution? Let us know in the comments below!