Difference between pages "5.5" and "5.7"

From The Algorithm Design Manual Solution Wiki
(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:
Apply binary search to find out transition point
+
<math>O(n+m)</math> is necessary and sufficient.
<pre>
+
Lower bound comes from potentially independent values along second diagonal --
Assume set indexes are zero based
+
upper bound comes from observing that we can eliminate either a row or a
FindIndex(A):
+
column in each comparison if we start from the lower left corner and walk
    1. low =  0, high =1
+
up or left.
    2. mid = (low + high)/2
 
    3. if(A[mid] > mid) then
 
            Index will lie in left half of the array
 
                high = mid-1
 
                Go to step 2.
 
        else if (A[mid] < mid) then
 
            Index will lie in right half of array
 
            low = mid + 1
 
        else
 
            return mid
 
</pre>
 
--[[User:Max|Max]] 07:31, 25 June 2010 (EDT)
 
  
 +
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