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.