https://algorist.com//algowiki/index.php?title=5.7&feed=atom&action=history5.7 - Revision history2024-03-28T11:12:17ZRevision history for this page on the wikiMediaWiki 1.34.2https://algorist.com//algowiki/index.php?title=5.7&diff=337&oldid=prevAlgowikiadmin: 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..."2020-09-21T00:56:23Z<p>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..."</p>
<p><b>New page</b></p><div><math>O(n+m)</math> is necessary and sufficient.<br />
Lower bound comes from potentially independent values along second diagonal --<br />
upper bound comes from observing that we can eliminate either a row or a<br />
column in each comparison if we start from the lower left corner and walk<br />
up or left.<br />
<br />
Having M[0..n-1][0..m-1] and a struct Point {int x, int y}, we could have the following solution:<br />
<br />
<br />
Point* findPosition(int key) {<br />
int row = 0, col = m-1;<br />
while (row < n && col >= 0) {<br />
if (M[row][col] == key) {<br />
return new Point(row,col); <br />
}<br />
else if (M[row][col] > key) {<br />
col--;<br />
}<br />
else row++; <br />
}<br />
return NULL;<br />
}<br />
<br />
Back to [[Chapter 5]]</div>Algowikiadmin