This is a
solution to
problem 26 on the
hard interview questions node. If you have not read the
question, the
following will make no
sense to you:
Consider the submatrix we will be searching in (which is initially the
entire matrix).
In the first column, find the largest element <= x (if there are
duplicates, choose the one with the lowest index). We know x must be in
this row or after (lower).
In the last column of the submatrix, find the smallest element >= x (if
there are duplicates, choose the one with the highest index). We know x
must be in this row or before.
Do the same thing with the first and last rows of the submatrix. We have
now defined a submatrix such that if x is in the matrix at all, it is in
this submatrix. Now either we have defined a smaller submatrix than the
one from the previous iteration, or we're done. If the submatrix is smaller, recurse.
If the submatrix is not smaller, then it must be that the entire leftmost
column and top row is <= x, and the entire rightmost column and bottom row
is >= x, or else we could've made it smaller. Then, the last element in
the top row (and symmetrically, the last element in the leftmost column)
is both <= and >= x, which implies that both are equal to x, so we can
return the coordinates of either (in a 1x1 submatrix, these are the same
coordinates).
If the submatrix has size zero (i.e., more recursion won't make it
smaller and there is no last element in the top row), the we can return
NONE, since x cannot be anywhere in the matrix.