```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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ``` ```#include using namespace std; struct MN{ int m; int n; }; /* PROBLEM: Given MxN matrix in which each row and each column is sorted in ascending order, write a method to find an element */ /* Proposition - Since rows (and columns are sorted), time complexity is O(M log(N)) - binary searching each row */ template /* NOTE: How to pass variable width 2D array. 2nd width must be specified */ struct MN * get(int a[][n], int k, int M, int N){ struct MN *result = new MN; result->m = -1; result->n = -1; /* Do a binary search on each row since rows (and columns too) are sorted. */ for(int i = 0; i < M; i++){ int lo = 0; int hi = N - 1; while(lo <= hi){ int mid = lo + (hi-lo)/2; if(k < a[i][mid]) hi = mid - 1; else if (k > a[i][mid]) lo = mid + 1; else{ result->m = i; result->n = mid; return result; } } } return result; } int main(){ const int M = 4; const int N = 3; // ISO C++ forbids variable-size array. Make them const int a[M][N] = {{1,2,3},{5,6,7},{10,20,30},{50,60,70}}; struct MN * result; int i, j; cout << "Matrix..." << endl; for(i = 0; i < M; i++){ for(j = 0; j < N; j++){ cout << a[i][j] << "\t"; } cout << endl; } int k = 30; result = get(a, k, M, N); cout << "Get " << k << " = (" << result->m << "," << result->n <<")" << endl; k = 31; result = get(a, k, M, N); cout << "Get " << k << " = (" << result->m << "," << result->n <<")"; return 0; } ```
 ```1 2 3 4 5 6 7 ``` ```Matrix... 1 2 3 5 6 7 10 20 30 50 60 70 Get 30 = (2,2) Get 31 = (-1,-1)```