Two-dimensional array search in sublinear time

Question

Today in an interview I was asked the following question:

Given an array of n of n integers that does not contain duplicates and values ​​that increase from left to right, and also from top to bottom, provide an algorithm that checks whether a given value is in the array.

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

This is an O (2n) solution, which I consider to be an optimal solution.

However, then the interviewer informed me that this problem can be solved in sub-linear time. I tried my brain how to do it, but I do not invent anything.

Is a sublinear solution possible or is it an optimal solution?

Answer 1

The thing to ask yourself is, what information does each comparison give you? This allows you to exclude the rectangle either from “top left” or “bottom right”.

Suppose you are comparing the value of "x" and it tells you what you are looking for more:

<Preview> XXX ... XXX ... XX x ... ...... ......

<i> 'x' is the test space
'X' - verification showed that this is not a possible location for your data
'.' - unknown

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

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

You will get a result, for example

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

Two rectangular spaces remain half-width and possibly full height. What can you do with this information?

I recommend repeating on the 2 received subelements '.'. BUT, now instead of selecting the middle column, you select the middle row to perform a binary search.

Thus, the resulting runtime of the rectangle N on M looks like this: T (N, M) = log (N) + T (M / 2, N) * 2

Note the change in indexes, because your recursive stack toggles between control columns and rows. The final runtime (I was not worried about recursion) should be something like T (M, N) = log (M) + log (N) (maybe this is not entirely true, but it will be similar).