Sorted Matrix.

[wildernesscat]

Another nice riddle for my collection. I didn't manage to solve it during the interview, but now I know the answer.

Suppose you have a NxN matrix of real numbers (M) such that:

• The individual columns of M are sorted (with the minimal element being at the top of each column and the maximal element being at the bottom)


• The individual rows of M are also sorted (with the minimal element being at the left of the row, and the maximal element being at the right).

Now, suppose you want to determine whether or not a given value x is in this Matrix.

You can do it in O(n logn) time, by simply iterating across the first row (column), and performing a binary search along the column (row). But there's a O(n) algorithm. What is it?