#include <iostream>
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 <size_t n> /* 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;
}