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