#include <iostream>
#include <vector>

using namespace std;

bool SearchMatrix(vector<vector<int> > &matrix, int target)
{
    int row = matrix.size();
    if(row <= 0) return false; 
    int col = matrix[0].size();
    if(col <= 0) return false;

    int low = 0;
    int high = row*col -1; //convert two dimension to one dimension
    int mid = 0;
    while(low <= high)
    {
        mid = (low + high) /2;
        //convert one dimension to two dimension
        int v = matrix[mid / col][mid % col];

        //binary search
        if (v < target)
            low = mid + 1;
        else if (v > target)
            high = mid - 1;
        else
            return true;
    }
        

    return false;
}


int main(int argc, char** argv)
{
    // [
    //     [1,   3,  5,  7],
    //     [11, 13, 17, 19],
    //     [23, 29, 31, 37]
    // ]

    vector<vector<int> > m(3);
	
    m[0].push_back(1);
    m[0].push_back(3);
    m[0].push_back(5);
    m[0].push_back(7);
    m[1].push_back(11);
    m[1].push_back(13);
    m[1].push_back(17);
    m[1].push_back(19);
    m[2].push_back(23);
    m[2].push_back(29);
    m[2].push_back(31);
    m[2].push_back(37);
	
	cout << (SearchMatrix(m, 7)? "true": "false")<<'\n';
	cout << (SearchMatrix(m, 21)? "true": "false")<<'\n';
	
    return 0;
}