Sorted Matrix Search

10.9 Sorted Matrix Search: Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

• Approach:

  • The big idea in this problem was recognizing that a 2d array can be read as a single dimension array and vise-versa. A sorted matrix down the diagonal also implies that we can aline each row next to each other sequentially and have a single sorted array.

struct MyException : public exception {
    const char* what() const throw() {
        return "Vector was empty";
    }
};

pair<int, int> d1_to_d2(int index_d1, int dim) {
    int row = index_d1 / dim;
    int col = index_d1 % dim;
    return make_pair(row, col);
}

pair<int, int> matrix_search(vector<vector<int>> &nxnMatrix, int find, int low, int high) {
    if (high > low)
    {
        int middle = low + ((high - low) / 2);
        pair<int, int> d2 = d1_to_d2(middle, nxnMatrix.size());

        if (nxnMatrix.at(d2.first).at(d2.second) == find) {
            return d2;
        }
        else if (nxnMatrix.at(d2.first).at(d2.second) > find) {
            //search left
            return matrix_search(nxnMatrix, find, low, middle - 1);
        }
        else {
            //search right
            return matrix_search(nxnMatrix, find, middle + 1, high);
        }
    }
    return make_pair(INT_MIN, INT_MIN);
}

pair<int, int> matrix_search(vector<vector<int>> &nxnMatrix, int find) {
    if (nxnMatrix.empty()) {
        throw MyException();
    }
    return matrix_search(nxnMatrix, find, 0, (nxnMatrix.size() * nxnMatrix.at(0).size()) - 1);
}

int main() {
    vector<vector<int>> matrix = {
        { 1, 2, 3, 4, 5, 6  },
        { 7, 8, 9, 10,11,12 },
        { 13,14,15,16,17,18 },
        { 19,20,21,22,23,24 },
        { 25,26,27,28,29,30 },
        { 31,32,33,34,35,36 }
    };

    pair<int, int> loc = matrix_search(matrix, 30);
    cout << loc.first << " " << loc.second << endl;
    pause();
}