Difference between pages "5.5" and "5.7"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "Apply binary search to find out transition point <pre> Assume set indexes are zero based FindIndex(A): 1. low = 0, high =1 2. mid = (low + high)/2 3. if(A[mid] >...") |
(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...") |
||
Line 1: | Line 1: | ||
− | + | <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..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]] | Back to [[Chapter 5]] |
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