Difference between revisions of "TADM2E 4.35"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

Revision as of 18:13, 11 September 2014
<math>O(n+m)</math> is necessary and sufficient. Lower bound comes from potentially independent values along second diagonal  upper bound comes from observing that we can eliminate either a row or a column in each comparison if we start from the lower left corner and walk up or left.
Having M[0..n1][0..m1] and a struct Point {int x, int y}, we could have the following solution:
Point* findPosition(int key) {
int row = 0, col = m1; while (row < n && col >= 0) { if (M[row][col] == key) { return new Point(row,col); } else if (M[row][col] > key) { col; } else row++; } return NULL;
}