# Difference between revisions of "TADM2E 4.35"

From Algorithm Wiki

(Recovering wiki) |
|||

(2 intermediate revisions by 2 users not shown) | |||

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 7: | Line 7: | ||

Having M[0..n-1][0..m-1] and a struct Point {int x, int y}, we could have the following solution: | 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) { | + | |

− | + | 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; |

+ | } |

## Latest revision as of 13:00, 30 April 2015

$ 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; }