> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/binary-searching-and-sorting/matrix-search.md).

# Matrix Search

Given a matrix of integers **A** of size **N x M** and an integer **B**.

Write an efficient algorithm that searches for integar **B** in matrix **A**.

This matrix **A** has the following properties:

> 1. Integers in each row are sorted from left to right.
> 2. The **first integer** of each row is greater than or equal to the **last integer** of the previous row.

Return **1** if **B** is present in **A**, else return **0**.

**Note:** Rows are numbered from top to bottom and columns are numbered from left to right.

\
\
**Input Format**

```
The first argument given is the integer matrix A.
The second argument given is the integer B.
```

**Output Format**

```
Return 1 if B is present in A, else return 0.
```

**Constraints**

```
1 <= N, M <= 1000
1 <= A[i][j], B <= 10^6
```

**For Example**

```
Input 1:
    A = 
    [ [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]  ]
    B = 3
Output 1:
    1

Input 2:
    A = [   [5, 17, 100, 111]
            [119, 120,  127,   131]    ]
    B = 3
Output 2:
    0
```

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0)
            return false;
        int m = matrix.length, n = matrix[0].length;
        int start = 0, end = m * n - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            int x = mid / n, y = mid % n;
            if (matrix[x][y] == target)
                return true;
            else if (target < matrix[x][y])
                end = mid - 1;
            else
                start = mid + 1;
        }
        return false;
    }
}
```