<p>A matrix <span class="math-container">$M$</span> is <em>sorted</em> if <span class="math-container">$M_{i,j}\leq M_{i+1,j}$</span> and <span class="math-container">$M_{i,j}\leq M_{i,j+1}$</span>.</p>

<p>Consider the following problem.</p>

<blockquote>
  <p><strong>Search in a sorted matrix</strong></p>
  
  <p>Given a <span class="math-container">$n\times m$</span> sorted matrix <span class="math-container">$M$</span>, where <span class="math-container">$n\leq m$</span>.
  There is a hidden number <span class="math-container">$x$</span>. We have access to an oracle <span class="math-container">$f$</span>, where <span class="math-container">$f(y)$</span> returns if <span class="math-container">$y&lt; x$</span>, <span class="math-container">$y=x$</span> or <span class="math-container">$y&gt;x$</span>. Decide if <span class="math-container">$x$</span> is in <span class="math-container">$M$</span>.</p>
</blockquote>

<p>The native algorithm would be going through every element in the matrix, and call the oracle on the element. This takes <span class="math-container">$O(nm)$</span> time and <span class="math-container">$O(nm)$</span> oracle calls.</p>

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

<p>The best-known algorithm can achieve <span class="math-container">$O(\log m)$</span> oracle calls and <span class="math-container">$O(n\log \frac{m}{n})$</span> time. <a href="https://dl.acm.org/citation.cfm?id=127822" rel="nofollow noreferrer">See here</a>.
This is best possible, as one can show a <span class="math-container">$\Omega(\log m)$</span> lower bound on oracle calls and <span class="math-container">$\Omega(n\log \frac{m}{n})$</span> on running time.</p>

<p>The problem is about more refined running time.
The numbers that are no larger than <span class="math-container">$x$</span> form an (inverted) staircase shape that contains all elements no larger than <span class="math-container">$x$</span>. 
We measure the complexity of the problem by the <span class="math-container">$h$</span>, the number of steps of the staircase, and <span class="math-container">$k$</span>, the number of elements no larger than <span class="math-container">$x$</span>.</p>

<blockquote>
  <p><strong>Example:</strong> Let <span class="math-container">$x=11$</span> and <span class="math-container">$M$</span> is the matrix below. The staircase shape
  is highlighted. The staircase shape has <span class="math-container">$h=3$</span> steps, and there are <span class="math-container">$k=11$</span>
  elements in the staircase. </p>
  
  <p><a href="https://i.sstatic.net/0v0cQ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0v0cQ.png" alt="enter image description here"></a></p>
</blockquote>

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

<p>One can show <span class="math-container">$\Omega(m)$</span> is the lower bound on the number of oracle calls. </p>

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

<blockquote>
  <p>Is it possible to use <span class="math-container">$O(h\log \frac{k}{h^2})$</span> time and <span class="math-container">$O(\log m)$</span> oracle calls to search in a sorted matrix?</p>
</blockquote>

CC BY-SA 4.0
2019-03-09T02:15:57.790Z
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).
hengxin
CC BY-SA 4.0
2019-03-09T12:16:32.760Z
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.
Chao Xu
CC BY-SA 4.0
2019-03-11T14:36:12.223Z
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?
Peter Shor 
CC BY-SA 4.0
2019-03-11T15:06:16.617Z
@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.
Chao Xu
CC BY-SA 4.0
2019-03-13T15:42:58.107Z
@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.
Peter Shor 
CC BY-SA 4.0
2019-03-13T21:42:26.330Z
@PeterShor I have made some modifications, I hope it is more understandable...
Chao Xu
<search-problem>
Search in a sorted matrix
Chao Xu
# Search in a sorted matrix

(Asked by: username_0 on 2019-03-03)

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](https://dl.acm.org/citation.cfm?id=127822).
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](https://i.sstatic.net/0v0cQ.png)](https://i.sstatic.net/0v0cQ.png)

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?

**Tags:** search-problem

> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_2**: @username_0: 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.  
> **username_0**: @PeterShor I have made some modifications, I hope it is more understandable...  

---

## 0 answers

