#include #include using namespace std; #define MP make_pair #define FOR(i,x,n) for(int i=x;i pii; typedef vector vi; typedef vector vii; vii v; int value; pii bsearch(pii x, pii y) { pii m; pii t1,t2; if ( x == y && GI(x) != value) { return MP(-1,-1); } m.first = (x.first + y.first) / 2; m.second = (x.second + y.second) / 2; if ( GI(y) == value ) return y; if ( GI(x) == value) return x; else if ( m == x )return MP(-1,-1); if ( GI(m) value) { t1 = bsearch(x,MP(x.first,y.second)); if (t1.first != -1 ) return t1; t2 = bsearch(x,MP(y.first,x.second)); return t2; } else return m; } int main() { pii x1,x2, result; int n,m; freopen("in.txt","r", stdin); while ( cin >> n >> m >> value ) { x1 = MP(0,0); x2 = MP(n-1,m-1); v = vii(n); FR(i,n) { v[i] = vi(m); FR(j,m) { cin >> v[i][j]; } } result = bsearch(x1,x2); cout << result.first << " : " << result.second << endl; } return 0; }

I think I saw this question in cracking the code interview.

Since the columns and rows are sorted you can go from the first row and last column and then look backwards: boolean FindElement(int[][] matrix, int elem, int M, int N) { int row = 0; int column = N-1; while (row = 0) if (matrix[row][column] == elem) return true; else if (matrix[row][column] > elem) column--; else row++; return false; }

binary search the first row and search the selected column

- Use binary search to locate which row the element could be in - Once you know the row from step above, use binary search on that row to know whether the number exists