StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I would use the divide-and-conquer strategy for this problem, similar to what you suggested, but the details are a bit different.</p> <p>This will be a recursive search on subranges of the matrix.</p> <p>At each step, pick an element in the middle of the range. If the value found is what you are seeking, then you're done.</p> <p>Otherwise, if the value found is less than the value that you are seeking, then you know that it is not in the quadrant above and to the left of your current position. So recursively search the two subranges: everything (exclusively) below the current position, and everything (exclusively) to the right that is at or above the current position.</p> <p>Otherwise, (the value found is greater than the value that you are seeking) you know that it is not in the quadrant below and to the right of your current position. So recursively search the two subranges: everything (exclusively) to the left of the current position, and everything (exclusively) above the current position that is on the current column or a column to the right.</p> <p>And ba-da-bing, you found it.</p> <p>Note that each recursive call only deals with the current subrange only, not (for example) ALL rows above the current position. Just those in the current subrange.</p> <p>Here's some pseudocode for you:</p> <pre><code>bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY) if (minX == maxX and minY == maxY and arr[minX,minY] != value) return false if (arr[minX,minY] > value) return false; // Early exits if the value can't be in if (arr[maxX,maxY] < value) return false; // this subrange at all. int nextX = (minX + maxX) / 2 int nextY = (minY + maxY) / 2 if (arr[nextX,nextY] == value) { print nextX,nextY return true } else if (arr[nextX,nextY] < value) { if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY)) return true return numberSearch(arr, value, nextX + 1, maxX, minY, nextY) } else { if (numberSearch(arr, value, minX, nextX - 1, minY, maxY)) return true reutrn numberSearch(arr, value, nextX, maxX, minY, nextY) } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload