Two dimensional array search in sub linear time

Question

Today I was asked the following question in an interview:

Given an n by n array of integers that contains no duplicates and values that increase from left to right as well as top to bottom, provide an algorithm that checks whether a given value is in the array.

The answer I provided was similar to the answer in this thread:
Algorithm: efficient way to search an integer in a two dimensional integer array?

This solution is O(2n), which I believed to be the optimal solution.

However, the interviewer then informed me that it is possible to solve this problem in sub linear time. I have racked my brain with how to go about doing this, but I am coming up with nothing.

Is a sub linear solution possible, or is this the optimal solution?

Answer 1

The thing to ask yourself is, what information does each comparison give you? It let's you eliminate the rectangle either "above to the left" or "below to the right".

Suppose you do a comparison at 'x' and it tells you what your are looking for is greater:

XXX...
XXX...
XXx...
......
......

'x' - checked space
'X' - check showed this is not a possible location for your data
'.' - still unknown

You have to use this information in a smart way to check the entire rectangle.

Suppose you do a binary search this way on the middle column...

You'll get a result like

XXX...
XXX...
XXX...
XXXXXX
...XXX
...XXX

Two rectangular spaces are left over of half width and possibly full height. What can you do with this information?

I recommend recurring on the 2 resulting subrectangles of '.'. BUT, now instead of choosing the middle column, you choose the middle row to do your binary search on.

So the resulting run time of an N by M rectangle looks like T(N, M) = log(N) + T(M/2, N)*2

Note the change in indexes because your recursion stack switches between checking columns and rows. The final run time (I didn't bother solving the recursion) should be something like T(M, N) = log(M) + log(N) (it's probably not exactly this but it will be similar).