Difference between revisions of "TADM2E 4.35"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
| − | + | <math>O(n+m)</math> is necessary and sufficient. | |
Lower bound comes from potentially independent values along second diagonal -- | Lower bound comes from potentially independent values along second diagonal -- | ||
upper bound comes from observing that we can eliminate either a row or a | upper bound comes from observing that we can eliminate either a row or a | ||
| Line 9: | Line 9: | ||
Point* findPosition(int key) { | Point* findPosition(int key) { | ||
int row = 0, col = m-1; | int row = 0, col = m-1; | ||
| − | while (row | + | while (row < n && col >= 0) { |
if (M[row][col] == key) { | if (M[row][col] == key) { | ||
return new Point(row,col); | return new Point(row,col); | ||
} | } | ||
| − | else if (M[row][col] | + | else if (M[row][col] > key) { |
col--; | col--; | ||
} | } | ||
Revision as of 18:23, 11 September 2014
$ O(n+m) $ 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..n-1][0..m-1] and a struct Point {int x, int y}, we could have the following solution:
Point* findPosition(int key) {
int row = 0, col = m-1;
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;
}
