TADM2E 4.35

From Algorithm Wiki
Revision as of 18:23, 11 September 2014 by Algowikiadmin (Talk | contribs)

Jump to: navigation, search

$ 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) {
    else row++; 
 return NULL;