Search in a sorted matrix with an oracle
Consider a infinite matrix . Another way to think about it is a function . A matrix is sorted if and .
Given a sorted matrix , and an oracle that takes returns if a value is or . Find the largest value no larger than .
Assuming there are at most elements no larger than , and we know the smallest and such that if or . Also, let be the smallest number such that . One can see that and .
Let's first consider the case when and is known and . It is Leetcode 240. Search a 2D Matrix II. However, our problem is more general, because comparison with can only be done through the oracle. Craig Gidney wrote about an optimal algorithm with running time, matrix access algorithm. However, the oracle access is too large. There are times where the oracle access is slow. For example, when using it as a subroutine for finding a bottleneck -link path. There is an algorithm with optimal running time and oracle access.
Let's consider a special case, where for some . This case was shown in . For each submatrix, the two vertices on the opposite diagonal indicates the largest and smallest element in the submatrix. Hence each matrix can be represented by two numbers, indicate the maximum and minimum. These numbers are called the representative of the matrix. The idea is we keep two numbers and , such that we know . The algorithm keep partition the matrix into small matrices, updating and , and discard matrices outside the range. We apply the following algorithm. Let consists of the multiset of representatives of the matrix, and be the representatives that lies inside . We find , the median of . Test if . If so, then updates to , otherwise updates to . This step is done twice. Now, we split the matrices with more than one element into equally sized matrices, and repeat the algorithm. Recall at all times, the matrices does not contain any element in are discarded.
There is at most iterations before range shrinks to a single element, hence at most oracle calls. The difficulty is to show that the overall time is only . Intuitively, in each iteration we quadruple the number of matrices, but we half it by two calls to the oracle. Therefore in steps we obtain roughly matrices. However, at this point, the matrices are all singletons, and no more matrix can be created. We will only decrease the number of matrices by each oracle call. Careful reader can trace the whole argument in Lemma 2.1 of .
For the more general case, one can find the proof in . Note the proof is for selection, but one can easily modify it to work for search.
Now, and is not known, but we can quickly using exponential search to find it. Indeed, we just have to apply exponential search in the first row and first column using the oracle. This gives us an extra oracle calls.
Let to be the number of elements no larger than . We can get running time relative to . Use exponential search until we find the first such that . So we can upper bound . Then one can solve the problem with matrices. One matrix and a matrix. The total running time is therefore . In fact, we get oracle calls and running time. Here we can take to be , and obtain time.
Note if we relax on number of oracle calls. I know how to get a running time.
Given and a sorted matrix such that the th row has elements no larger than . Let . We can find in time.
The idea is simple, we do exponential search on each row to find the largest element no larger than , but we reuse information from the previous row. This gives us the running time . The main difficulty is to show why is is .
If , then .
Once we show that, we can use the theorem to obtain running time.
In fact, we can also get a very simple algorithm with running time , where is the number of stairs in the staircase shape. However, it also uses oracle calls. The idea is to use exponential search to find the boundary of the staircase, but we switch between boundaries: horizontal then vertical. It is open if we can obtain running time and oracle calls.
The careful reader might observe the known search algorithms follow the exact same structure as algorithms for selection. Indeed, we are doing selection but we do not know the rank of the element. Intuitively, many selection algorithm, the rank is only used to remove the correct set of candidates. Hence this suggest one can modify the algorithm to use the oracle call in place of the rank.
 G.N. Frederickson, S. Zhou, Optimal parametric search for path and tree partitioning, CoRR. abs/1711.00599 (2017).
 G. Frederickson, D. Johnson, Generalized selection and ranking: Sorted matrices, SIAM Journal on Computing. 13 (1984) 14–30 10.1137/0213002.
 R. Jacob, Binary search on two-dimensional data, Technische Universität München, 2008.