6
$\begingroup$

A matrix $M$ is sorted if $M_{i,j}\leq M_{i+1,j}$ and $M_{i,j}\leq M_{i,j+1}$.

Consider the following problem.

Search in a sorted matrix

Given a $n\times m$ sorted matrix $M$, where $n\leq m$. There is a hidden number $x$. We have access to an oracle $f$, where $f(y)$ returns if $y< x$, $y=x$ or $y>x$. Decide if $x$ is in $M$.

The native algorithm would be going through every element in the matrix, and call the oracle on the element. This takes $O(nm)$ time and $O(nm)$ oracle calls.

One can get much better in terms of oracle calls. A simple algorithm is to sort all elements in the matrix in $O(nm \log nm)$ time, and then use the oracle $O(\log nm)=O(\log m)$ times to do a binary search on the sorted list.

The best-known algorithm can achieve $O(\log m)$ oracle calls and $O(n\log \frac{m}{n})$ time. See here. This is best possible, as one can show a $\Omega(\log m)$ lower bound on oracle calls and $\Omega(n\log \frac{m}{n})$ on running time.

The problem is about more refined running time. The numbers that are no larger than $x$ form an (inverted) staircase shape that contains all elements no larger than $x$. We measure the complexity of the problem by the $h$, the number of steps of the staircase, and $k$, the number of elements no larger than $x$.

Example: Let $x=11$ and $M$ is the matrix below. The staircase shape is highlighted. The staircase shape has $h=3$ steps, and there are $k=11$ elements in the staircase.

enter image description here

One can obtain a $O(h\log \frac{k}{h^2})$ time algorithm for the problem by using exponential search to find the boundary of the staircase. This never worse than $O(n\log \frac{m}{n})$, and significantly better when $h$ is small. However, the algorithm has to use the oracle $O(h\log \frac{k}{h^2})$ times.

One can show $\Omega(m)$ is the lower bound on the number of oracle calls.

Can we get the best of both worlds? A faster running time together with small number of oracle calls?

Is it possible to use $O(h\log \frac{k}{h^2})$ time and $O(\log m)$ oracle calls to search in a sorted matrix?

$\endgroup$
  • $\begingroup$ If you are interested, here is an algorithm using $\le n + m - 1$ queries for an $n \times m$ matrix: Each time we query the element at the left bottom corner, say $y$. This helps us to eliminate one row or one column, depending on whether $y > x$ or $y < x$. Furthermore, this algorithm is optimal for $n \times n$ square matrices $M$ by an adversary argument: If $i + j \le n - 1$, then $x > M[i][j]$, else $x < M[i][j]$. See Problem 5.24 of the textbook "Computer Algorithms" by Sara Baase and Allen Van Gelder (3rd Edition). $\endgroup$ – hengxin Mar 9 at 2:15
  • $\begingroup$ Thank you for the comment. Indeed it is optimal for nxn matrix. Note the stated running time in my problem is always no worse than that algorithm. $\endgroup$ – Chao Xu Mar 9 at 12:16
  • $\begingroup$ Suppose I tell you that all the numbers are above the right diagonal are 0, and all the numbers below the diagonal are 3. On the diagonal there is exactly one 2, and all the other numbers are 1. How are you going to find the 2 in less than $n/2$ expected oracle calls? $\endgroup$ – Peter Shor Mar 11 at 14:36
  • $\begingroup$ @PeterShor Matrix access does not use oracle calls. I can take all $n$ elements in the diagonal, sort them, and use the oracle for binary search on this sorted list. $\endgroup$ – Chao Xu Mar 11 at 15:06
  • $\begingroup$ @Chao Xu: You confused me by saying "Given an oracle that decides if a point is inside the staircase." I see that's obviously not what you mean by "oracle call", but I can't figure out what you do mean. $\endgroup$ – Peter Shor Mar 13 at 15:42

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.