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, returntrue.

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 forfront == end. This ensures that when the front reaches the end, and the element is not contained within this final index, then false is returned.

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

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);
}