# 74 Search a 2D Matrix

Write an efficient algorithm that searches for a value in anmxnmatrix. This matrix has the following properties:

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

For example,

Consider the following matrix:

```
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
```

Given **target**=`3`, return`true`.

**Complexity**: O(logN) time and space

**The Idea**: Treat the matrix as a regular array. In memory, this is how a matrix is actually laid out. If we do this, the problem simply becomes a plain old 1d binary search problem with a few minor modifications. First, we need to address 1D->2D indexing. To do this, we check to see how many rows fit the index. This will becomes the row index. The column index then simply becomes the remainder of the row size. Finally, there is an edge case with finding the maximum element in the matrix. This is why I placed another if else condition for`front == end`. This ensures that when the front reaches the end, and the element is not contained within this final index, then false is returned.

```cpp
bool binary_matrix_search(int front, int end, vector<vector<int>>& matrix, int target)
{
    if (front <= end) {
        int row_size = matrix.at(0).size();
        int middle = ((end - front) >> 1) + front;

        int cur_elm = matrix[middle / row_size][middle % row_size];

        if (target == cur_elm) return true;
        else if (front == end) return false;
        else if (target < cur_elm) return binary_matrix_search(front, middle, matrix, target);
        else return binary_matrix_search(middle + 1, end, matrix, target);
    }
    else return false;
}

bool searchMatrix(vector<vector<int>>& matrix, int target) 
{
    if (matrix.empty()) return false;

    int front = 0;
    int end = matrix.size() * matrix.at(0).size() - 1;
    return binary_matrix_search(front, end, matrix, target);
}
```

**Some Tests**

```cpp
int main()
{
    vector<vector<int>> matrix2 = {
        { 1 }
    };
    assert(searchMatrix(matrix2, 0) == false);

    vector<vector<int>> matrix = {
        { 1, 3, 5, 7 },
        { 10, 11, 16, 20 },
        { 23, 30, 34, 50 }
    };

    assert(searchMatrix(matrix, 50) == true);
    for (auto i : matrix) {
        for (auto j : i) {
            assert(searchMatrix(matrix, j) == true);
            cout << "passed: " << j << endl;
        }
    }
    assert(searchMatrix(matrix, 27) == false);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/74-search-a-2d-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.