Matrix-Search-D&C

#include <iostream>
#include <vector>

using namespace std;

pair<int, int> find(vector<vector<int>>& X, int k, int top_left_i, int top_left_j, int bottom_right_i, int bottom_right_j) {
    int m_i = (top_left_i + bottom_right_i) / 2;
    int m_j = (top_left_j + bottom_right_j) / 2;

    if (X[m_i][m_j] == k) {
        return make_pair(m_i, m_j);
    }

    if (top_left_i == bottom_right_i && top_left_j == bottom_right_j) {
        return make_pair(-1, -1);  // not found
    }

    if (top_left_i > bottom_right_i || top_left_j > bottom_right_j) {
        return make_pair(-1, -1);  // not found
    }

    if (X[m_i][m_j] > k) {
        pair<int, int> pos = find(X, k, top_left_i, top_left_j, m_i - 1, m_j - 1);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }

        pos = find(X, k, m_i, top_left_j, bottom_right_i, m_j - 1);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }

        pos = find(X, k, top_left_i, m_j, m_i - 1, bottom_right_j);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }
    }
    else {
        pair<int, int> pos = find(X, k, m_i + 1, m_j + 1, bottom_right_i, bottom_right_j);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }

        pos = find(X, k, m_i + 1, top_left_j, bottom_right_i, m_j);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }

        pos = find(X, k, top_left_i, m_j + 1, m_i, bottom_right_j);
        if (pos != make_pair(-1, -1)) {
            return pos;
        }
    }

    return make_pair(-1, -1);  // not found
}