Difference between revisions of "5.7"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
(Created page with "<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 el...")
 
(No difference)

Latest revision as of 00:56, 21 September 2020

[math]\displaystyle{ 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..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;
   }

Back to Chapter 5